【树状数组】bzoj2789 [Poi2012]Letters

#include<cstdio>
#include<queue>
using namespace std;
#define N 1000001
typedef long long ll;
queue<int>qs[26];
ll ans;
int n,A[N];
char a[N],b[N];
int d[N];
void Update(int p){for(;p<=n;p+=(p&(-p))) ++d[p];}
int Query(int p){int res=0; for(;p;p-=(p&(-p))) res+=d[p]; return res;}
int main()
{
	scanf("%d%s%s",&n,a+1,b+1);
	for(int i=1;i<=n;++i) qs[b[i]-‘A‘].push(i);
	for(int i=1;i<=n;++i)
	  {
	  	A[i]=qs[a[i]-‘A‘].front();
	  	qs[a[i]-‘A‘].pop();
	  }
	for(int i=1;i<=n;++i)
	  {
	  	Update(A[i]);
	  	ans+=(ll)(i-Query(A[i]));
	  }
	printf("%lld\n",ans);
	return 0;
}