題目
bzoj2555
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
題意
給定一個初始字元串，支援2個操作。在後面添加一個字元串或詢問一個字元串出現了多少次。 強制線上。
字元串最終長度 <= 600000，詢問次數<= 10000,詢問總長度<= 3000000。
題解
首先想到的是字尾自動機，每個節點維護一個size，添加一個字元時将它parent的size都加一。詢問時沿着字尾自動機走，輸出最後一個節點的size即可。
但暴力維護會TLE，于是隻能上LCT了。
注意不僅要link新加進來的節點，在字尾自動機建構時parent改變後也要及時link和cut。還有就是複制節點q時所得到的nq的size是為0的（我最初設的是1，wa了好久，其實想想暴力維護時是怎麼做的就明白了。），當link q與nq時會将nq的size累加上q的size。
下面貼代碼：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define maxn 1200100
char s[];
int n,len,ans,mask,last=,tot=;
struct LCT{
int son[maxn][],size[maxn],f[maxn],tag[maxn];
#define root(x) (son[f[x]][0]!=x&&son[f[x]][1]!=x)
void push_down(int x){
if(tag[x]==)return;
size[son[x][]]+=tag[x];
tag[son[x][]]+=tag[x];
size[son[x][]]+=tag[x];
tag[son[x][]]+=tag[x];
tag[x]=;
}
void push_up(int x){
if(!root(x))push_up(f[x]);
push_down(x);
}
void rt(int x,int k){
int y=f[x],z=f[y];
son[y][k^]=son[x][k];
f[son[x][k]]=y;
son[x][k]=y;
f[y]=x; f[x]=z;
if(son[z][]==y)son[z][]=x;
else if(son[z][]==y)son[z][]=x;
push_down(y);
push_down(x);
}
void splay(int x){
push_up(x);
while(!root(x)){
int y=f[x],z=f[y];
if(root(y)&&son[y][]==x)rt(x,);
else if(root(y)&&son[y][]==x)rt(x,);
else if(son[z][]==y&&son[y][]==x)rt(y,),rt(x,);
else if(son[z][]==y&&son[y][]==x)rt(x,),rt(x,);
else if(son[z][]==y&&son[y][]==x)rt(x,),rt(x,);
else rt(y,),rt(x,);
}
}
void access(int x){
for(int y=;x;x=f[x]){
splay(x);
son[x][]=y;
push_down(x);
y=x;
}
}
void link(int x,int y){
access(y);splay(y);f[x]=y;
size[y]+=size[x]; tag[y]+=size[x];
}
void cut(int x,int y){
access(y); splay(x); f[x]=;
size[y]-=size[x]; tag[y]-=size[x];
}
}t;
struct SAM{
int go[maxn][],pre[maxn],step[maxn];
void add(int x){
int p=last,np=++tot;
step[np]=step[p]+;
for(;p!=&&go[p][x]==;p=pre[p])go[p][x]=np;
if(p==)pre[np]=;
else{
int q=go[p][x];
if(step[q]==step[p]+)pre[np]=q;
else{
int nq=++tot;
memcpy(go[nq],go[q],sizeof(go[q]));
pre[nq]=pre[q];
t.link(nq,pre[q]);
step[nq]=step[p]+;
t.cut(q,pre[q]);
pre[q]=pre[np]=nq;
t.link(q,nq);
for(;go[p][x]==q;p=pre[p])go[p][x]=nq;
}
}
last=np;
t.size[last]=;
t.link(last,pre[last]);
}
int solve(char s[]){
int len=strlen(s),p=;
for(int i=;i<len;i++){
if(go[p][s[i]-'A']==)return ;
p=go[p][s[i]-'A'];
}
t.access(p);
t.splay(p);
return t.size[p];
}
}sam;
void trans(int mask){
scanf("%s",s);
len=strlen(s);
for(int j=;j<len;j++){
mask=(mask*+j)%len;
char t=s[j];
s[j]=s[mask];
s[mask]=t;
}
}
int main(){
scanf("%d",&n);
scanf("%s",s);
len=strlen(s);
for(int i=;i<len;i++) sam.add(s[i]-'A');
for(int i=;i<=n;i++){
scanf("%s",s);
if(s[]=='A'){
trans(mask);
len=strlen(s);
for(int j=;j<len;j++)
sam.add(s[j]-'A');
}else{
trans(mask);
ans=sam.solve(s);
printf("%d\n",ans);
mask^=ans;
}
}
return ;
}