2555: SubString
Time Limit: 30 Sec Memory Limit: 512 MB
Submit: 1620 Solved: 471
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
注意这个mask不会在函数内改变……
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=;
int cnt,last;
int FA[maxn],CH[maxn][],len[maxn],rt[maxn];
int fa[maxn],ch[maxn][],add[maxn],key[maxn],flip[maxn]; void Add(int x,int d){
if(!x)return;
key[x]+=d;
add[x]+=d;
} void Flip(int x){
swap(ch[x][],ch[x][]);
flip[x]^=;
} void Push_down(int x){
if(add[x]){
Add(ch[x][],add[x]);
Add(ch[x][],add[x]);
add[x]=;
}
if(flip[x]){
Flip(ch[x][]);
Flip(ch[x][]);
flip[x]=;
}
} void Rotate(int x){
int y=fa[x],g=fa[y],c=ch[y][]==x;
ch[y][c]=ch[x][c^];fa[ch[y][c]]=y;
ch[x][c^]=y;fa[y]=x;fa[x]=g;
if(rt[y])rt[y]=false,rt[x]=true;
else ch[g][ch[g][]==y]=x;
} void P(int x){
if(!rt[x])P(fa[x]);
Push_down(x);
} void Splay(int x){
P(x);
for(int y=fa[x];!rt[x];Rotate(x),y=fa[x])
if(!rt[y])Rotate((ch[fa[y]][]==y)==(ch[y][]==x)?y:x);
} void Access(int x){
int y=;
while(x){
Splay(x);
rt[ch[x][]]=true;
rt[ch[x][]=y]=false;
x=fa[y=x];
}
} void Lca(int &x,int &y){
Access(y);y=;
while(true){
Splay(x);
if(!fa[x])break;
rt[ch[x][]]=true;
rt[ch[x][]=y]=false;
x=fa[y=x];
}
} void Make_rt(int x){
Access(x);
Splay(x);
Flip(x);
} void Change(int x,int y,int d){
Lca(x,y);key[x]+=d;
Add(y,d);Add(ch[x][],d);
} void Link(int x,int y){
Make_rt(x);
Splay(x);
fa[x]=y;
Change(,y,key[x]);
} void Cut(int x,int y){
Make_rt(x);
Splay(y);
fa[ch[y][]]=fa[y];
fa[y]=;rt[ch[y][]]=true;
ch[y][]=;
Change(,y,-key[x]);
} struct SAM{
void Init(){
memset(FA,,sizeof(FA));
memset(CH,,sizeof(CH));
memset(rt,-,sizeof(rt));
last=cnt=;
} void Insert(int c){
int p=last,np=last=++cnt;len[np]=len[p]+;key[np]=;
while(p&&!CH[p][c])CH[p][c]=np,p=FA[p];
if(!p)FA[np]=;
else{
int q=CH[p][c];
if(len[p]+==len[q])
FA[np]=q;
else{
int nq=++cnt;len[nq]=len[p]+;
memcpy(CH[nq],CH[q],sizeof(CH[q]));
FA[nq]=FA[q];FA[q]=FA[np]=nq; Link(nq,FA[nq]);Cut(q,FA[nq]);Link(q,nq); while(CH[p][c]==q)
CH[p][c]=nq,p=FA[p];
}
}
Link(np,FA[np]);
}
void Extend(char *s){
int l=strlen(s);
for(int i=;i<l;i++)
Insert(s[i]-'A');
} int Solve(char *s){
int l=strlen(s),p=;
for(int i=,c;i<l;i++){
c=s[i]-'A';
if(!CH[p][c])return ;
else p=CH[p][c];
}
Splay(p);
return key[p];
}
}sam; char s[maxn];
char op[];
int ans,mask,Q; void Decode(char *str,int t){
int l=strlen(str);
for(int i=;i<l;i++){
t=(t*+i)%l;
swap(str[i],str[t]);
}
} int main(){
sam.Init();
scanf("%d",&Q);
scanf("%s",s);
sam.Extend(s);
while(Q--){
scanf("%s",op);
scanf("%s",s);Decode(s,mask);
if(op[]=='A')
sam.Extend(s);
else{
ans=sam.Solve(s);
printf("%d\n",ans);
mask^=ans;
}
}
return ;
}