P3531 [POI2012]LIT-Letters

题面

给出两个长度相同的的只含大写字母的字符串 \(a, b\)，每次可以交换 \(a\) 中相邻两个字符，求最少的交换次数，使得 \(a\) 交换后的得到的字符串与 \(b\) 相同。

思路

建议先完成这两道题：

• P1908 逆序对
• P1966 [NOIP2013 提高组] 火柴排队

交换相邻的字母，很像逆序对问题。可是，如何转换成逆序对呢？

可以将 \(b\) 字符串编个号，比如说假如 \(b\) 字符串的内容是 "BCA"，那么可以令 \(B=1,C=2,A=3\)，然后在对 \(a\) 数组按这个编号进行转换，比如说假如 \(a\) 字符串是 "ABC"，那么转换后就是 \(\{3,1,2\}\)。

然后就是水的逆序对了，时间复杂度是 \(O(n \log n)\)。

#include
#define int long long
using namespace std;

int n;
pair a[1000005],b[1000005];
int c[1000005];
int t[4000005];
char aaa[1000005],bbb[1000005];
map translator;

inline int lowbit(int x){
	return x&(-x);
}
void update(int p,int v){
	while(p<=n){
		t[p]+=v;
		p+=lowbit(p);
	}
}
int query(int p){
	int ans=0;
	while(p>0){
		ans+=t[p];
		p-=lowbit(p);
	}
	return ans;
}

int solve(){
	int ans=0;
	for(int i=1;i<=n;i++) {
		ans+=i-1-query(c[i]-1);
		update(c[i],1);
	}
	return ans;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
    cin>>aaa+1;
    cin>>bbb+1;
    for(int i=1;i<=n;i++){
		char t;
		t=aaa[i];
		a[i]=make_pair(t-'A'+1,i);
	}
    for(int i=1;i<=n;i++){
		char t;
		t=bbb[i];
		b[i]=make_pair(t-'A'+1,i);
	}
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	for (int i=1;i<=n;i++) {
		c[a[i].second]=b[i].second;
	}
	cout<