SubString
给你一个字符串init，要求你支持两个操作
- 在当前字符串的后面插入一个字符串
- 询问字符串s在当前字符串中出现了几次？(作为连续子串)
你必须在线支持这些操作。
分析
所谓的出现次数就是这个字符串在SAM上跑完对应的right集合。要支持及时插入，也就是要动态的维护Parent树的形态。
“动态”，“树”，我们很明显本能的会想到动态树。此处动态树肯定是LCT。
回顾Parent tree的性质, 一个父亲节点所表示的所有子串的出现位置不同，并且为其所有子节点的子串的出现位置的集合的并。这个性质就是解决这道题的关键。
所以我们可以用link-cut-tree维护这一棵Parent tree（因为要支持加边，同时必须在线）。在插入一个字符时, 对其所对应的parent tree上到根的路径上的节点全部加1. 查询时直接输出一个点上的值即可。
路径修改，单点查询，LCT的权能。
当然这个LCT不是我们平时见到的那种LCT。原因：
- 这是一棵有向树。换而言之，这题不可能有换根操作。（SAM的Parent树的形态是相对固定的）
- 注意link和cut的时候要消除之前的影响，体现在标记上。
- 查询的时候如果没有转移边(trans)可走，证明这个子串就没有出现过。
查询的时候要把到根路径上的标记清空，这个splay一下就行了。
时间复杂度(O((Q+n)log n+L))
代码
两天没打代码SAM都生疏了，竟然把后面的边连向了cur……
int mask;
char s[3000001];
void gets(int mask){ // edit 1: afferent "mask"
scanf("%s",s);int n=strlen(s);
for(int i=0;i<n;++i){
mask=(mask*131+i)%n;
std::swap(s[i],s[mask]);
}
}
co int N=12e5;
// Link Cut Tree
namespace T{
int fa[N],ch[N][2],val[N],tag[N];
#define lc ch[x][0]
#define rc ch[x][1]
void add(int x,int v) {if(x) val[x]+=v,tag[x]+=v;}
void pushdown(int x){
if(tag[x]){
add(lc,tag[x]),add(rc,tag[x]);
tag[x]=0;
}
}
bool nroot(int x) {return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
void rotate(int x){
int y=fa[x],z=fa[y],l=x==ch[y][1],r=l^1;
if(nroot(y)) ch[z][y==ch[z][1]]=x;fa[x]=z;
ch[y][l]=ch[x][r],fa[ch[x][r]]=y;
ch[x][r]=y,fa[y]=x;
}
void splay(int x){
static int st[N];
int y=x,z=0;
st[++z]=y;
while(nroot(y)) st[++z]=y=fa[y];
while(z) pushdown(st[z--]);
for(;nroot(x);rotate(x)){
y=fa[x],z=fa[y];
if(nroot(y)) rotate(y==ch[z][1]^x==ch[y][1]?x:y);
}
}
void access(int x){
for(int y=0;x;x=fa[y=x]) splay(x),rc=y;
}
void link(int x,int y){ // virtual edge
fa[x]=y,access(y),splay(y),add(y,val[x]);
}
void cut(int x){
access(x),splay(x),add(lc,-val[x]);
fa[lc]=0,lc=0;
}
}
// Suffix Automaton
namespace SAM{
int last=1,tot=1;
int ch[N][26],fa[N],len[N];
void extend(int c){
int p=last,cur=last=++tot;
len[cur]=len[p]+1,T::val[cur]=1;
for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=cur;
if(!p) fa[cur]=1,T::link(cur,1);
else{
int q=ch[p][c];
if(len[q]==len[p]+1) fa[cur]=q,T::link(cur,q);
else{
int clone=++tot;
memcpy(ch[clone],ch[q],sizeof ch[q]);
fa[clone]=fa[q],len[clone]=len[p]+1,T::link(clone,fa[q]);
fa[cur]=fa[q]=clone,T::link(cur,clone),T::cut(q),T::link(q,clone);
for(;ch[p][c]==q;p=fa[p]) ch[p][c]=clone; // edit 2:clone
}
}
}
void build(){
scanf("%s",s);int n=strlen(s);
for(int i=0;i<n;++i) extend(s[i]-'A');
}
void add(){
gets(mask);int n=strlen(s);
for(int i=0;i<n;++i) extend(s[i]-'A');
}
int query(){
gets(mask);int n=strlen(s);
int p=1;
for(int i=0;i<n;++i)if(!(p=ch[p][s[i]-'A'])) return 0;
T::splay(p);
return T::val[p];
}
}
int main(){
int q=read<int>();
SAM::build();
while(q--){
scanf("%s",s);
if(*s=='A') SAM::add();
else{
int ans=SAM::query();
printf("%d
",ans);
mask^=ans;
}
}
return 0;
}