bzoj2555 SubString

Description

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

Input

    第一行一个数Q表示操作个数
    第二行一个字符串表示初始字符串init
    接下来Q行，每行2个字符串Type,Str
    Type是ADD的话表示在后面插入字符串。
    Type是QUERY的话表示询问某字符串在当前字符串中出现了几次。
    为了体现在线操作，你需要维护一个变量mask，初始值为0

读入串Str之后，使用这个过程将之解码成真正询问的串TrueStr。
    询问的时候，对TrueStr询问后输出一行答案Result
    然后mask = mask xor Result
    插入的时候，将TrueStr插到当前字符串后面即可。

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

Output

Sample Input

2
A
QUERY B
ADD BBABBBBAAB

Sample Output

HINT

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

新加数据一组--2015.05.20

正解：后缀自动机+$link-cut tree$。

首先我们可以对原串构后缀自动机，然后我们可以发现一个子串的个数就是它的$right$集合的大小，也就是$parent$树的子树。

那么我们可以每次新建点连边的时候用$LCT$来维护子树大小，直接连边以后它父亲到根的路径$+1$就行了。

  1 #include <bits/stdc++.h>
  2 #define il inline
  3 #define RG register
  4 #define ll long long
  5 #define N (1200010)
  6 #define M (3000010)
  7 
  8 using namespace std;
  9 
 10 int Q,len,ans,mask;
 11 char s[M],type[M];
 12 
 13 struct Link_Cut_Tree{
 14   
 15   int ch[N][2],fa[N],st[N],val[N],tag[N],top;
 16   
 17   il void add(RG int x,RG int v){
 18     if (x) val[x]+=v,tag[x]+=v; return;
 19   }
 20   
 21   il int isroot(RG int x){
 22     return ch[fa[x]][0]!=x && ch[fa[x]][1]!=x;
 23   }
 24   
 25   il void pushdown(RG int x){
 26     add(ch[x][0],tag[x]),add(ch[x][1],tag[x]),tag[x]=0; return;
 27   }
 28   
 29   il void rotate(RG int x){
 30     RG int y=fa[x],z=fa[y],k=ch[y][0]==x;
 31     if (!isroot(y)) ch[z][ch[z][1]==y]=x;
 32     fa[x]=z,ch[y][k^1]=ch[x][k],fa[ch[x][k]]=y;
 33     ch[x][k]=y,fa[y]=x; return;
 34   }
 35   
 36   il void splay(RG int x){
 37     RG int top=0; st[++top]=x;
 38     for (RG int i=x;!isroot(i);i=fa[i]) st[++top]=fa[i];
 39     for (RG int i=top;i;--i) if (tag[st[i]]) pushdown(st[i]);
 40     while (!isroot(x)){
 41       RG int y=fa[x],z=fa[y];
 42       if (!isroot(y)) rotate((ch[z][0]==y)^(ch[y][0]==x) ? x : y);
 43       rotate(x);
 44     }
 45     return;
 46   }
 47   
 48   il void access(RG int x){
 49     RG int t=0;
 50     while (x) splay(x),ch[x][1]=t,t=x,x=fa[x];
 51     return;
 52   }
 53   
 54   il void link(RG int x,RG int y){
 55     fa[x]=y,access(y),splay(y),add(y,val[x]); return;
 56   }
 57   
 58   il void cut(RG int x){
 59     access(x),splay(x),add(ch[x][0],-val[x]);
 60     fa[ch[x][0]]=0,ch[x][0]=0; return;
 61   }
 62   
 63   il int query(RG int x){ splay(x); return val[x]; }
 64   
 65 }LCT;
 66 
 67 struct Suffix_Automaton{
 68   
 69   int ch[N][26],fa[N],l[N],la,tot;
 70   
 71   il void init(){ la=++tot; return; }
 72   
 73   il void add(RG int c){
 74     RG int p=la,np=++tot; la=np,l[np]=l[p]+1,LCT.val[np]=1;
 75     for (;p && !ch[p][c];p=fa[p]) ch[p][c]=np;
 76     if (!p){ LCT.link(np,fa[np]=1); return; }
 77     RG int q=ch[p][c];
 78     if (l[q]==l[p]+1) LCT.link(np,fa[np]=q); else{
 79       RG int nq=++tot; l[nq]=l[p]+1;
 80       memcpy(ch[nq],ch[q],sizeof(ch[q]));
 81       LCT.cut(q),LCT.link(nq,fa[nq]=fa[q]);
 82       LCT.link(q,fa[q]=nq),LCT.link(np,fa[np]=nq);
 83       for (;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
 84     }
 85     return;
 86   }
 87   
 88   il int query(){
 89     RG int cur=1;
 90     for (RG int i=0;i<len;++i)
 91       if (!(cur=ch[cur][s[i]-'A'])) return 0;
 92     return LCT.query(cur);
 93   }
 94   
 95 }SAM;
 96 
 97 il void trans(RG int mask){
 98   for (RG int i=0;i<len;++i)
 99     swap(s[i],s[mask=(mask*131+i)%len]);
100   return;
101 }
102 
103 int main(){
104 #ifndef ONLINE_JUDGE
105   freopen("substring.in","r",stdin);
106   freopen("substring.out","w",stdout);
107 #endif
108   cin>>Q,scanf("%s",s),len=strlen(s),SAM.init();
109   for (RG int i=0;i<len;++i) SAM.add(s[i]-'A');
110   while (Q--){
111     scanf("%s%s",type,s),len=strlen(s),trans(mask);
112     if (type[0]=='A') for (RG int i=0;i<len;++i) SAM.add(s[i]-'A');
113     if (type[0]=='Q') printf("%d
",ans=SAM.query()),mask^=ans;
114   }
115   return 0;
116 }