传送门
如果这题可以离线的话当然就SAM+线段树合并了，但是它居然来了个强制在线，给了个神奇的解码函数，我没有注意mask是传的参数，交上去直接WA，怀疑人生。
当然这题要强制在线的话就用LCT来维护parent树，维护子树和就行了，LCT的link和cut与sam里fa指针的动作保持一致就很好维护了。
当然询问的时候可以先断开p与fa[p]的链接，然后将p设为根，查p的子树和就ok，然后再连接p和fa[p]。
不知道为什么不开O2直接超时，开了O2速度能跑进第一页……可能是因为makeroot操作有点多余吧，我看题解有说没有必要makeroot的，但是我有点没想明白为什么，而且我不makeroot还会错。
#include <bits/stdc++.h>
using namespace std;
const int N=4e6+10;
struct LCT{
int fa[N*2],ch[N*2][2],f[N*2],f2[N*2],rev[N*2],val[N*2];
#define ls(x) (ch[x][0])
#define rs(x) (ch[x][1])
#define ident(p,f) (ch[f][1]==p)
#define connect(p,f,k) (ch[fa[p]=f][k]=p)
#define ntroot(p) (ls(fa[p])==p||rs(fa[p])==p)
inline void pushup(int p) {f[p]=f[rs(p)]+f[ls(p)]+val[p]+f2[p];}
inline void Rev(int p){swap(ls(p),rs(p));rev[p]^=1;}
inline void pushdw(int p){if(rev[p]) Rev(ls(p)),Rev(rs(p));rev[p]=0;}
inline void rotate(int p){
int f=fa[p],ff=fa[f],k=ident(p,f);
connect(ch[p][k^1],f,k);
fa[p]=ff;
if(ntroot(f)) ch[ff][ident(f,ff)]=p;
connect(f,p,k^1);
pushup(f),pushup(p);
}
inline void pushall(int p){if(ntroot(p)) pushall(fa[p]);pushdw(p);}
inline void splay(int p){
pushall(p);
while(ntroot(p)){
int f=fa[p],ff=fa[f];
if(ntroot(f)) ident(p,f)^ident(f,ff)?rotate(p):rotate(f);
rotate(p);
}
}
void access(int p){
for(int t=0;p;p=fa[t=p])
splay(p),f2[p]+=f[rs(p)]-f[t],
rs(p)=t,pushup(p);
}
void makert(int p){
access(p);splay(p);Rev(p);
}
int findrt(int p){
access(p);splay(p);
while(ls(p)) p=ls(p),pushdw(p);
splay(p);return p;
}
void split(int p,int q){
makert(p);access(q);splay(q);
}
void link(int p,int q){
makert(p);makert(q);fa[p]=q;
f2[q]+=f[p];pushup(q);
}
void cut(int p,int q){
split(p,q);fa[p]=ls(q)=0;pushup(q);
}
}lct;
int n,m,mask;
char s[N];
struct SuffixAutomaton{
int last=1,tot=1,fa[N*2],len[N*2],ch[N*2][2];
int newnode(int x){fa[++tot]=fa[x];len[tot]=len[x];memcpy(ch[tot],ch[x],sizeof(ch[tot]));return tot;}
void append(int c){
int p=last,np=last=newnode(0);
len[np]=len[p]+1; lct.val[np]=1;
for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
if(!p) fa[np]=1;
else if(len[ch[p][c]]==len[p]+1) fa[np]=ch[p][c];
else{
int q=ch[p][c],nq=newnode(q);len[nq]=len[p]+1;
lct.cut(q,fa[q]);
lct.link(nq,fa[q]);
fa[q]=fa[np]=nq;
lct.link(q,nq);
for(;p&&ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
}
lct.link(np,fa[np]);
}
int ask(){
int p=1,flag=1;
for(int i=0;i<n;i++)
if(ch[p][s[i]-'A']) p=ch[p][s[i]-'A'];
else {flag=0;break;}
if(!flag) return 0;
lct.cut(p,fa[p]);
lct.splay(p);
int res=lct.f[p];
lct.link(p,fa[p]);
return res;
}
}sam;
void decode(int mask){
for(int i=0;i<n;i++){
mask=(mask*131+i)%n;
swap(s[i],s[mask]);
}
}
int main(){
scanf("%d",&m);
scanf("%s",s);
n=strlen(s);
for(int i=0;i<n;i++) sam.append(s[i]-'A');
while(m--){
char opt[10];
scanf("%s%s",opt,s);
n=strlen(s);decode(mask);
if(opt[0]=='A'){
for(int i=0;i<n;i++) sam.append(s[i]-'A');
}
else{
int res=sam.ask();
printf("%d
",res);
mask^=res;
}
}
return 0;
}