Magic FZU - 2280 字典树加树状数组

题意：给n个长度<=1000的字符串S[i](仅由小写字母构成)，每个字符串有权值w[i]
      有两种操作
      2 k 选中第k个字符串，问你有多少个字符串满足w[i]<=w[k]而且S[k]是S[i]的后缀
      1 k y 把第k个字符串的权值修改为y

用树状数组维护权值出现的个数，因为要满足后缀关系，所以用字典树反向插入，在节点位置标记，使得之后插入的字符串到达该节点时，更新个数，
插入的顺序是长度从小到大，因为有相同字符串存在，所以为每个字符串标记一下在字典树中最后到达的节点上的值（也就是第一个相同串的序号），这样就能统一处理了。详见代码。

#include <iostream>  #include <cstdio>  #include <cstdlib>  #include <cstring>  #include <algorithm>  #include <vector>  #include <map>  #include <cmath>  #include <set>  #include <queue>  using namespace std;    const int INF=1e9+10;  const double EPS = 1e-10;    typedef long long ll;  const int mod=1e9+7;int n;int ch[100005][27],sz;int bit[1005][1005],slen[1005],vec[1005],wt[1005];int val[100005];int End[1005];bool cmp(int a,int b){    return slen[a]<slen[b];}void add(int k,int x,int d){    while(x<=1000){        bit[k][x]+=d;x+=x&-x;    }}int getsum(int k,int x){    int ret=0;    while(x){        ret+=bit[k][x];        x-=x&-x;    }    return ret;}void insert(int k,char *s){    int len=slen[k];    int u=0;    for(int i=len-1;i>=0;i--){        int c=s[i]-'a';        if(!ch[u][c]){            memset(ch[sz],0,sizeof(ch[sz]));            ch[u][c]=sz++;        }        u=ch[u][c];        if(val[u]){            add(val[u],wt[k],1);        }    }    if(!val[u]){        val[u]=k;        add(k,wt[k],1);    }    End[k]=val[u];}void update(int k,char *s,int v){    int len=slen[k],u=0;    for(int i=len-1;i>=0;i--){        int c=s[i]-'a';        u=ch[u][c];        if(val[u]){            add(val[u],wt[k],-1);            add(val[u],v,1);        }    }    wt[k]=v;}char s[1005][1005];int main(){    int T;    scanf("%d",&T);    while(T--){        sz=1;        memset(ch[0],0,sizeof(ch[0]));        memset(bit,0,sizeof(bit));        memset(val,0,sizeof(val));        scanf("%d",&n);        for(int i=1;i<=n;i++){            scanf("%s %d",s[i],&wt[i]);            slen[i]=strlen(s[i]);            vec[i]=i;        }        sort(vec+1,vec+n+1,cmp);        for(int i=1;i<=n;i++){            insert(vec[i],s[vec[i]]);        }        int t;        scanf("%d",&t);        while(t--){            int op;            scanf("%d",&op);            if(op==1){                int k,v;                scanf("%d %d",&k,&v);                update(k,s[k],v);            }else{                int k;                scanf("%d",&k);                printf("%d\n",getsum(End[k],wt[k]));            }        }    }    return 0;}