自动搬运

查看原文

来自洛谷，原作者为

	姬小路秋子 **

搬运于2025-08-24 21:49:55，当前版本为作者最后更新于2018-07-20 20:06:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

交换相邻两个数就决定了是求逆序对

对于A中的一个字符在B中的位置，我们可以发现同一个字符肯定是按从前往后的顺序出现在B中的。

比如A串ABABA，B串BAABA

我们肯定是把A中的第一个A放在B中的第一个A上，依次类推。

因为如果第一个A放在了后面，那么就有可能产生更对逆序对（因为你把大的数放在了前面）。由此得证。

好吧其实也挺显然的，我也是无聊才来水水题解的。

下面是代码（楼上那位ZJa队爷不放真是可惜了）

#include<bits/stdc++.h>
using namespace std;
int c[26][1000001],n,a[1000001],d[26];
long long f[1000001];
int lowbit(int x){
	return x&(-x);
}
void insert(int x){
	int i;
	for(i=x;i<=n;i+=lowbit(i))f[i]++;
}
long long query(int x){
	int i;
	long long ans=0;
	for(i=x;i;i-=lowbit(i))ans+=f[i];
	return ans;
}
int main(){
	long long ans=0;
	int i;
	char s[1000001],s1[1000001];
	scanf("%d",&n);
	scanf("%s",s);
	scanf("%s",s1);
	for(i=0;i<n;i++)
		c[s[i]-'A'][++c[s[i]-'A'][0]]=i;
	for(i=0;i<n;i++){
		a[i+1]=c[s1[i]-'A'][++d[s1[i]-'A']]+1;
	}	
	for(i=1;i<=n;i++){
		//printf("%d\n",i);
		ans+=query(n)-query(a[i]-1);
		//printf("%d\n",i);
		insert(a[i]);
	}
	printf("%lld",ans);
}