【树状数组】bzoj2789 [Poi2012]Letters

处理数组A,A[i]表示字符串a的第i个字符排序后应去的位置,队列可。

对于多次出现的字符,其在a中的顺序和在b中的顺序应该是一一对应的。

#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;
}
上一篇:uva 1151(最小生成树,枚举子集)


下一篇:springboot集成spring data ElasticSearch