2789: [Poi2012]Letters
stupid_lulu
posted @ 2013年3月19日 15:34
in poi
, 967 阅读
其实有更方便的作法,但我写的hash挂链+树状数组维护。。
太傻叉了。。直接贴代码。。
#include<cstdio> int t[1000003]; int head[1000002],next[1000002]; char s1[1000002],s2[1000002]; int n; long long ans=0; int lowbit(int x){return x&(-x);} void add(int x,int c){ while (x<=n){ t[x]+=c; x+=lowbit(x); } } int ques(int x){ int ans=0; while (x>0){ ans+=t[x]; x-=lowbit(x); } return ans; } int main(){ scanf("%d",&n); scanf("%s",s1); scanf("%s",s2); //puts(s1); //puts(s2); for (int i=n;i>=1;i--){ int x=s1[i-1]-'A'; //printf("%d\n",x); next[i]=head[x]; head[x]=i; } for (int i=1;i<=n;i++){ int z=s2[i-1]-'A'; //printf("%d\n",z); int x=head[z]; x+=ques(x); //printf("%d\n",x); //printf("%d %d\n",x,i); if (x>i) ans+=x-i; int y=i+ques(i); //printf("l=%d r=%d\n",i,head[z]); if (x>i){ add(1,1); add(head[z]+1,-1); } head[z]=next[head[z]]; } printf("%lld\n",ans); }