思路

我是一个懒人，我不想做太难的题，所以我先把问题简化一下：如果每一次的花费都是$1$那答案会是什么？开一个树状数组，$s_i$表示目前访问过多少个数字小于$i$的球，按照顺序访问每一个球，每一次答案都加上访问过的数字比它大的球的个数 $sum(n)-sum(x_i)$，读者自证不难毕竟如果有一个求在他的左侧，又比它大，必然最后会到达他的右侧，这之间就必然会有一次他们的交换。

但是人不能这么懒，我们尝试再回想一下这道题本身。很好发现本题的答案一定比刚刚的问题的答案小，且正好是交换两个相邻的颜色一样的球的数量。怎么求呢？回归原本的思路，我们可以很好的找出每一个球有多少个球与它需要交换，如果说我们按照颜色来访问而非顺序呢？每一次都只访问颜色一样的球，访问完再清空不就可以了吗？

ACcode

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+10;
int s[N],c[N],x[N],n;
vector<int>G[N];
void add(int x,int k){for(;x<=n;x+=x&-x)s[x]+=k;}
int sum(int x)
{
	int res=0;
	for(;x;x-=x&-x)res+=s[x];
	return res;
}
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)scanf("%lld",&c[i]),G[c[i]].push_back(i);
	for(int i=1;i<=n;i++)scanf("%lld",&x[i]);
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		ans+=sum(n)-sum(x[i]);
		add(x[i],1);
	}
	memset(s,0,sizeof(s));
	for(int i=1;i<=n;i++)
	{
		for(int j:G[i])
		{
			ans-=sum(n)-sum(x[j]);
			add(x[j],1);
		}
		for(int j:G[i])add(x[j],-1);
	}
	printf("%lld\n",ans);
	return 0;
}

如果说你不是懒人，可以想一下如果每一次操作所需花费是$c_i+1-c_i$该如何计算（好像也不难）