懒得写背景了，给你一个字符串init，要求你支持两个操作
    
    (1):在当前字符串的后面插入一个字符串
    
    (2):询问字符串s在当前字符串中出现了几次？(作为连续子串)
    
    你必须在线支持这些操作。
    

    第一行一个数Q表示操作个数
    
    第二行一个字符串表示初始字符串init
    
    接下来Q行，每行2个字符串Type,Str 
    
    Type是ADD的话表示在后面插入字符串。
    
    Type是QUERY的话表示询问某字符串在当前字符串中出现了几次。
    
    为了体现在线操作，你需要维护一个变量mask，初始值为0
   
    
    读入串Str之后，使用这个过程将之解码成真正询问的串TrueStr。
    询问的时候，对TrueStr询问后输出一行答案Result
    然后mask = mask xor Result  
    插入的时候，将TrueStr插到当前字符串后面即可。

HINT:ADD和QUERY操作的字符串都需要解压
   

 40 % 的数据字符串最终长度 <= 20000，询问次数<= 1000，询问总长度<= 10000

    

100 % 的数据字符串最终长度 <= 600000，询问次数<= 10000,询问总长度<= 3000000

新加数据一组--2015.05.20

   

Ctsc模拟赛By 洁妹

  1 /*by SilverN*/  2 #include<algorithm>  3 #include<iostream>  4 #include<cstring>  5 #include<cstdio>  6 #include<cmath>  7 #include<vector>  8 using namespace std;  9 const int mxn=1100010; 10 struct LCT{ 11     int ch[mxn][2],fa[mxn]; 12     int val[mxn],mk[mxn]; 13     bool rev[mxn]; 14     int st[mxn],top; 15     inline bool isroot(int x){ 16         return (ch[fa[x]][0]!=x)&&(ch[fa[x]][1]!=x); 17     } 18     inline void PD(int x){ 19         if(mk[x]){ 20             int &lc=ch[x][0],&rc=ch[x][1]; 21             mk[lc]+=mk[x];mk[rc]+=mk[x]; 22             val[lc]+=mk[x];val[rc]+=mk[x]; 23             mk[x]=0; 24         } 25         if(rev[x]){ 26             int &lc=ch[x][0],&rc=ch[x][1]; 27             swap(lc,rc); 28             rev[lc]^=1;rev[rc]^=1; 29             rev[x]^=1; 30         } 31         return; 32     } 33     void rotate(int x){ 34         int y=fa[x],z=fa[y],lc,rc; 35         if(ch[y][0]==x)lc=0;else lc=1; rc=lc^1; 36         if(!isroot(y)){ 37             ch[z][ch[z][1]==y]=x; 38         } 39         fa[x]=z;fa[y]=x; 40         fa[ch[x][rc]]=y; 41         ch[y][lc]=ch[x][rc]; 42         ch[x][rc]=y; 43         return; 44     } 45     void Splay(int x){ 46         st[top=1]=x; 47         for(int i=x;!isroot(i);i=fa[i])st[++top]=fa[i]; 48         while(top)PD(st[top--]); 49         while(!isroot(x)){ 50             int y=fa[x],z=fa[y]; 51             if(!isroot(y)){ 52                 if((ch[y][0]==x)^(ch[z][0]==y))rotate(x); 53                 else rotate(y); 54             } 55             rotate(x); 56         } 57         return; 58     } 59     void access(int x){ 60         for(int y=0;x;x=fa[x]){ 61             Splay(x); 62             ch[x][1]=y; 63             y=x; 64         } 65         return; 66     } 67     void link(int x,int y){ 68         fa[x]=y;access(y);Splay(y); 69         val[y]+=val[x];mk[y]+=val[x]; 70         return; 71     } 72     void cut(int x,int y){ 73         access(y);Splay(y); 74         if(ch[y][0]==x){ 75             fa[x]=ch[y][0]=0; 76             val[x]-=val[y];mk[x]-=val[y]; 77         } 78         return; 79     } 80     inline int query(int x){ 81         access(x);Splay(x); 82         return val[x]; 83     } 84 }Lt; 85 struct SAM{ 86     int t[mxn][26],fa[mxn],l[mxn],sz[mxn]; 87     int S,last,cnt; 88     void init(){S=last=cnt=1;return;} 89     void add(int c){ 90         int p=last,np=++cnt;last=np; 91         l[np]=l[p]+1; 92         Lt.val[np]=1; 93         sz[np]++; 94         for(;p && !t[p][c];p=fa[p]){ 95             t[p][c]=np; 96         } 97         if(!p){ 98             fa[np]=S; 99             Lt.link(np,S);100         }101         else{102             int q=t[p][c];103             if(l[q]==l[p]+1){104                 fa[np]=q;105                 Lt.link(np,q);106             }107             else{108                 int nq=++cnt;109                 l[nq]=l[p]+1;110                 memcpy(t[nq],t[q],sizeof t[q]);111                 //112                 Lt.link(nq,fa[q]);113                 Lt.cut(fa[q],q);114                 Lt.link(np,nq);115                 Lt.link(q,nq);116                 //117                 fa[nq]=fa[q];118                 fa[q]=fa[np]=nq;119                 for(;p && t[p][c]==q;p=fa[p]){120                     t[p][c]=nq;121                 }122             }123         }124         return;125     }126     int query(char *s){127         int len=strlen(s);128         int now=S;129         for(int i=0;i<len;i++){130             if(t[now][s[i]-‘A‘]){131                 now=t[now][s[i]-‘A‘];132             }133             else return 0;134         }135         return Lt.query(now);136     }137 }sa;138 char s[3000002],op[10];139 void decode(char *c,int mask){//解码 140     int len=strlen(s);141     for(int j=0;j<len;j++){142         mask=(mask*131+j)%len;143         char t=c[j];144         c[j]=c[mask];145         c[mask]=t;146     }147     return;148 }149 int Q,tlen,mask=0;150 int main(){151     int i,j;152     scanf("%d",&Q);153     scanf("%s",s);154     sa.init();155     int len=strlen(s);tlen=len;156     for(i=0;i<len;i++) sa.add(s[i]-‘A‘);157     while(Q--){158         scanf("%s%s",op,s);159         decode(s,mask);//解码 160         if(op[0]==‘A‘){161             int len=strlen(s);162             tlen+=len;163             for(i=0;i<len;i++){164                 sa.add(s[i]-‘A‘);165             }166         }167         else{168             int res=sa.query(s);169             mask^=res;170             printf("%d\n",res);171         }172     }173     return 0;174 }175