题目描述
(1):在当前字符串的后面插入一个字符串
(2):询问字符串s在当前字符串中出现了几次？(作为连续子串)
你必须在线支持这些操作。
题解
做法很自然，建出后缀自动机，维护每个节点的right集合，对于询问直接在sam上跑就好了。
然后它是在线的，得用LCT维护。
然后细节极多，首先必须维护好树的形态，也就是说不能makeroot，所以我的link就长这样。
inline void link(int x,int y){
access(x);splay(x);access(y);splay(y);
f[x]=y;si[y]+=size[x];pushup(y);
}
然后cut长这样
inline void cut(int x,int y){
access(x);splay(x);
f[tr[x][]]=;tr[x][]=;
pushup(x);
}
所以在这颗LCT中，每个点的左儿子维护的是它的父亲，然后我们在算子树和的时候把左儿子扣掉就好了。
断断续续淦了三天，极菜。
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 1300002
using namespace std;
int size[N],ch[N][],tr[N][],fa[N],si[N],last,cnt,n,l[N],q,f[N],val[N];
int mark;
char s[N],qs[];
inline void pushup(int x){size[x]=size[tr[x][]]+size[tr[x][]]+si[x]+val[x];}
inline bool ge(int x){return tr[f[x]][]==x;}
inline bool isroot(int x){return tr[f[x]][]!=x&&tr[f[x]][]!=x;}
inline void rotate(int x){
int y=f[x],o=ge(x);
if(isroot(x))return;
tr[y][o]=tr[x][o^];f[tr[y][o]]=y;
if(!isroot(y))tr[f[y]][ge(y)]=x;f[x]=f[y];
f[y]=x;tr[x][o^]=y;pushup(y);pushup(x);
}
inline void splay(int x){
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(int x){
for(int y=;x;y=x,x=f[x]){
splay(x);
si[x]+=size[tr[x][]];si[x]-=size[y];tr[x][]=y;
pushup(x);
}
}
inline void link(int x,int y){
access(x);splay(x);access(y);splay(y);
f[x]=y;si[y]+=size[x];pushup(y);
}
inline void cut(int x,int y){
access(x);splay(x);
f[tr[x][]]=;tr[x][]=;
pushup(x);
}
void Decode(char *ch,int mask){
int l=strlen(ch+);
for(int i=;i<l;++i){
mask=(mask*+i)%l;
swap(ch[i+],ch[mask+]);
}
}
inline void ins(int x){
int p=last,np=++cnt;last=np;l[np]=l[p]+;size[np]=val[np]=;
for(;p&&!ch[p][x];p=fa[p])ch[p][x]=np;
if(!p)fa[np]=,link(np,);
else{
int q=ch[p][x];
if(l[p]+==l[q])fa[np]=q,link(np,q);
else{
int nq=++cnt;l[nq]=l[p]+;
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(int n){
int now=;
for(int i=;i<=n;++i)if(ch[now][s[i]-'A'])now=ch[now][s[i]-'A'];else return ;
access(now);splay(now);
return size[now]-size[tr[now][]];
}
int main(){
scanf("%d",&q);
scanf("%s",s+);n=strlen(s+);last=cnt=;
for(int i=;i<=n;++i)ins(s[i]-'A');
while(q--){
scanf("%s",qs);scanf("%s",s+);n=strlen(s+);
Decode(s,mark);
if(qs[]=='Q'){
int x=query(n);mark^=x;printf("%d\n",x);
}
else for(int i=;i<=n;++i)ins(s[i]-'A');
}
return ;
}