Description
懒得写背景了，给你一个字符串init，要求你支持两个操作
(1):在当前字符串的后面插入一个字符串
(2):询问字符串s在当前字符串中出现了几次？(作为连续子串)
你必须在线支持这些操作。
Solution
思路比较直观啊
首先没有插入的话,预处理好每个点 \(|right|\) 就好了
如果有插入的话我们发现实际上就是维护一个子树大小
每一次插入一个节点就相当于把父亲到根路径上的权值全部 \(+1\)
我们用 \(LCT\) 维护这个加边删边和路径加法的操作
每一次询问就是先找到这个串对应的节点 \(x\),如果没找到答案就是 \(0\),否则就是 \(|Right_x|\) 了
这题是有根树,不需要 \(makeroot\) 操作,写起来比较舒服
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
namespace LCT{
int ch[N][2],fa[N],la[N],w[N];
inline bool isrt(int x){return ch[fa[x]][0]!=x && ch[fa[x]][1]!=x;}
inline void mark(int x,int t){la[x]+=t;w[x]+=t;}
inline void pushdown(int x){
if(!la[x])return ;
mark(ch[x][0],la[x]);mark(ch[x][1],la[x]);
la[x]=0;
}
inline void rotate(int x){
int y=fa[x];bool t=ch[y][1]==x;
ch[y][t]=ch[x][!t];fa[ch[y][t]]=y;
ch[x][!t]=y;fa[x]=fa[y];
if(!isrt(y))ch[fa[y]][ch[fa[y]][1]==y]=x;
fa[y]=x;
}
inline void Push(int x){
if(!isrt(x))Push(fa[x]);
pushdown(x);
}
inline void splay(int x){
Push(x);
while(!isrt(x)){
int y=fa[x],p=fa[y];
if(isrt(y))rotate(x);
else if((ch[p][0]==y)==(ch[y][0]==x))rotate(y),rotate(x);
else rotate(x),rotate(x);
}
}
inline void access(int x){
int y=0;
while(x)splay(x),ch[x][1]=y,x=fa[y=x];
}
inline void link(int x,int y){
fa[x]=y;access(y);splay(y);splay(x);mark(y,w[x]);
}
inline void cut(int x){
access(x);splay(x);mark(ch[x][0],-w[x]);fa[ch[x][0]]=0;ch[x][0]=0;
}
inline int query(int x){
splay(x);return w[x];
}
}
char s[N],op[10];int Q,mask=0;
inline void decode(){
int len=strlen(s),t=mask;
for(int j=0;j<len;j++){
t=(t*131+j)%len;
swap(s[j],s[t]);
}
}
int ch[N][27],fa[N],len[N],cur=1,cnt=1;
inline void ins(int c){
int p=cur;cur=++cnt;len[cur]=len[p]+1;LCT::w[cur]=1;
for(;p && !ch[p][c];p=fa[p])ch[p][c]=cur;
if(!p)fa[cur]=1,LCT::link(cur,1);
else{
int q=ch[p][c];
if(len[q]==len[p]+1)fa[cur]=q,LCT::link(cur,q);
else{
int nt=++cnt;len[nt]=len[p]+1;
memcpy(ch[nt],ch[q],sizeof(ch[q]));
LCT::cut(q);LCT::link(nt,fa[q]);LCT::link(q,nt);LCT::link(cur,nt);
fa[nt]=fa[q];fa[q]=fa[cur]=nt;
for(;p && ch[p][c]==q;p=fa[p])ch[p][c]=nt;
}
}
}
inline int solve(int len){
int p=1;
for(int i=0;i<len;i++){
int c=s[i]-'A';
if(ch[p][c])p=ch[p][c];
else return 0;
}
return LCT::query(p);
}
int main(){
freopen("pp.in","r",stdin);
freopen("pp.out","w",stdout);
cin>>Q;
scanf("%s",s);
for(int i=0,le=strlen(s);i<le;i++)ins(s[i]-'A');
while(Q--){
scanf("%s%s",op,s);
decode();
int len=strlen(s),la;
if(op[0]=='A')for(int i=0;i<len;i++)ins(s[i]-'A');
else printf("%d\n",la=solve(len)),mask^=la;
}
return 0;
}