摘要：
您必须在线支持这些操作。这个问题的解决是很自然的。建立一个后缀自动机，维护每个节点的正确集合，并直接在sam上运行查询。然后它是在线的，需要由LCT维护。inlinevoidlink{access；dispay；access；display；f[x]=y；si[y]+=size[x]；pushup；}然后，剪切长度为inlinevoidcut｛access；play；f[tr[x][0]]=0；tr[x][0]=0；pushup；｝所以在这个LCT中，每个点的左子保持其父，然后我们可以在对算子树求和时扣除左子。经过三天的间歇生长，它非常美味。
题目描述
(1):在当前字符串的后面插入一个字符串
(2):询问字符串s在当前字符串中出现了几次？(作为连续子串)
你必须在线支持这些操作。
题解
做法很自然，建出后缀自动机，维护每个节点的right集合，对于询问直接在sam上跑就好了。
然后它是在线的，得用LCT维护。
然后细节极多，首先必须维护好树的形态，也就是说不能makeroot，所以我的link就长这样。
inline void link(int x,inty){ access(x);splay(x);access(y);splay(y); f[x]=y;si[y]+=size[x];pushup(y); }
然后cut长这样
inline void cut(int x,inty){ access(x);splay(x); f[tr[x][0]]=0;tr[x][0]=0; pushup(x); }
所以在这颗LCT中，每个点的左儿子维护的是它的父亲，然后我们在算子树和的时候把左儿子扣掉就好了。
断断续续淦了三天，极菜。
#include<iostream>#include<cstdio>#include<cstring> #define N 1300002 using namespacestd; int size[N],ch[N][26],tr[N][2],fa[N],si[N],last,cnt,n,l[N],q,f[N],val[N]; intmark; char s[N],qs[10]; inline void pushup(int x){size[x]=size[tr[x][0]]+size[tr[x][1]]+si[x]+val[x];} inline bool ge(int x){return tr[f[x]][1]==x;} inline bool isroot(int x){return tr[f[x]][0]!=x&&tr[f[x]][1]!=x;} inline void rotate(intx){ int y=f[x],o=ge(x); if(isroot(x))return; tr[y][o]=tr[x][o^1];f[tr[y][o]]=y; if(!isroot(y))tr[f[y]][ge(y)]=x;f[x]=f[y]; f[y]=x;tr[x][o^1]=y;pushup(y);pushup(x); } inline void splay(intx){ while(!isroot(x)){ int y=f[x]; if(isroot(y))rotate(x); else rotate(ge(x)==ge(y)?y:x),rotate(x); } } inline void access(intx){ for(int y=0;x;y=x,x=f[x]){ splay(x); si[x]+=size[tr[x][1]];si[x]-=size[y];tr[x][1]=y; pushup(x); } } inline void link(int x,inty){ access(x);splay(x);access(y);splay(y); f[x]=y;si[y]+=size[x];pushup(y); } inline void cut(int x,inty){ access(x);splay(x); f[tr[x][0]]=0;tr[x][0]=0; pushup(x); } void Decode(char *ch,intmask){ int l=strlen(ch+1); for(int i=0;i<l;++i){ mask=(mask*131+i)%l; swap(ch[i+1],ch[mask+1]); } } inline void ins(intx){ int p=last,np=++cnt;last=np;l[np]=l[p]+1;size[np]=val[np]=1; for(;p&&!ch[p][x];p=fa[p])ch[p][x]=np; if(!p)fa[np]=1,link(np,1); else{ int q=ch[p][x]; if(l[p]+1==l[q])fa[np]=q,link(np,q); else{ int nq=++cnt;l[nq]=l[p]+1; memcpy(ch[nq],ch[q],sizeof(ch[q])); int y=fa[q];cut(q,y);link(nq,y); fa[nq]=fa[q];fa[q]=fa[np]=nq; link(q,nq);link(np,nq); for(;ch[p][x]==q;p=fa[p])ch[p][x]=nq; } } } int query(intn){ int now=1; for(int i=1;i<=n;++i)if(ch[now][s[i]-'A'])now=ch[now][s[i]-'A'];else return 0; access(now);splay(now); return size[now]-size[tr[now][0]]; } intmain(){ scanf("%d",&q); scanf("%s",s+1);n=strlen(s+1);last=cnt=1; for(int i=1;i<=n;++i)ins(s[i]-'A'); while(q--){ scanf("%s",qs);scanf("%s",s+1);n=strlen(s+1); Decode(s,mark); if(qs[0]=='Q'){ int x=query(n);mark^=x;printf("%d ",x); } else for(int i=1;i<=n;++i)ins(s[i]-'A'); } return 0; }