2789: [Poi2012]Letters

其实有更方便的作法，但我写的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);
}