相邻交换-逆序对。

可以类比题目：P1966 火柴排队(NOIP2013)

$a$ 和 $b$ 排序后，希望调整 $b$ 的顺序，让 $b$ 中第 $i$ 小的位置 $idx$ 与 $a$ 中第 $i$ 小的位置 $idx$ 相同。

也就是：$q[a[i].idx] = b[i].idx$。

求q的逆序对。

相同数字按照出现的id从小到大依次排序即可。

#include <bits/stdc++.h>
using namespace std;
int read()
{
	int x = 0, f = 1;
	char c = getchar();
	while(c<'0' || c>'9'){if(c=='-')f=-1; c = getchar();}
	while(c>='0'&&c<='9'){x = x*10+c-'0'; c = getchar();}
	return x*f;
}
/*
参考1966火柴排队
3531 POI2012 letters
xa:  1   2   3   4
ra： 4   1   3   2
 a： 73  13  43  23
 b： 11  31  21  71
xb:  1   2    3   4

a':  13 23  43  73
xa:  2  4   3    1


 b'： 11  21  31  71
xb':  1   3   2   4

q[xa[i]] = xb[i]
q:    4   1   2   3

*/
typedef long long LL;
const LL MAXN = 1000005;
struct Node
{
	char val;
	LL idx;
	bool operator < (const Node &t) const
	{
		if(val==t.val) return idx<t.idx;
		return val<t.val;
	}
}a[MAXN],b[MAXN];
LL q[MAXN],c[MAXN];
int N;
int lowbit(LL x){return x&(-x);}
LL sum(LL x)
{
	LL res = 0;
	while(x>0)
	{
		res += c[x];
		x-= lowbit(x);
	}
	return res;
}
void add(LL x, LL d)
{
	while(x<=N)
	{
		c[x] += d;
		x += lowbit(x);
	}
}
char str[MAXN];
int main()
{
	N = read();
	scanf("%s",str);
	for(LL i = 1; i<=N; i++)
	{
		a[i].val = str[i-1];
	 	a[i].idx = i;
    }
    scanf("%s",str);
    for(LL i = 1; i<=N; i++)
    {
		b[i].val = str[i-1];
		b[i].idx = i;
	}
	sort(a+1,a+N+1); sort(b+1,b+N+1);
	for(LL i = 1; i<=N; i++) q[a[i].idx] = b[i].idx;
	LL ans = 0;
	for(LL i = N; i>=1; i--)
	{
		ans += sum(q[i]-1);
		add(q[i],1);
	}
	cout << ans <<endl;
	return 0;
}