【题目链接】
http://www.lydsy.com/JudgeOnline/problem.php?id=2555
【题意】
给定一个字符串，可以随时插入字符串，提供查询s在其中作为连续子串的出现次数。
【思路】
子串的出现次数，这使我们想到了后缀自动机，如果没有插入操作，则出现次数为字符串对应节点|right|集的大小。
Right的递推方法为：|fa->right| <- |right|
如果暴力做的话，可以每一次插入都重新计算right。时间复杂度为O(mn)。
因为需要不断地插入字符串，所以parent树会发生变化，我们考虑使用LCT维护parent树。SAM中插入字符串时需要改变父亲，对应到LCT中即切断原树中本来的父亲，连接新的父亲，最后还应该把np的所有fa的|right|加1，对应于LCT中的一次区间加值。
这样只需要用LCT维护一个值与一个懒标记即可。
注意LCT原来的Link是连接两个点，而这里的Link需要切断原来的父亲后连接新父亲。
【代码】
#include<cstdio>
#include<cstring>
#include<iostream>
#define FOR(a,b,c) for(int a=b;a<=c;a++)
#define trav(u,i) for(int i=front[u];i;i=e[i].nxt)
using namespace std; const int N = 4e6+; namespace LCT { struct Node {
Node *ch[],*fa;
int v,add,rev;
Node() ;
void addv(int x) {
v=v+x;
add=add+x;
}
void reverse() {
rev^=;
swap(ch[],ch[]);
}
void up_push() {
if(fa->ch[]==this||fa->ch[]==this)
fa->up_push();
if(add) {
ch[]->addv(add);
ch[]->addv(add);
add=;
}
if(rev) {
ch[]->reverse();
ch[]->reverse();
rev=;
}
}
void maintain() {
}
} *null=new Node ;
Node:: Node() {
fa=ch[]=ch[]=null;
add=v=rev=;
} void rot(Node* o,int d) {
Node *p=o->fa;
p->ch[d]=o->ch[d^];
o->ch[d^]->fa=p;
o->ch[d^]=p;
o->fa=p->fa;
if(p==p->fa->ch[])
p->fa->ch[]=o;
else if(p==p->fa->ch[])
p->fa->ch[]=o;
p->fa=o;
p->maintain();
}
void splay(Node* o) {
o->up_push();
Node *nf,*nff;
while(o->fa->ch[]==o||o->fa->ch[]==o) {
nf=o->fa,nff=nf->fa;
if(o==nf->ch[]) {
if(nf==nff->ch[]) rot(nf,);
rot(o,);
} else {
if(nf==nff->ch[]) rot(nf,);
rot(o,);
}
}
o->maintain();
}
void Access(Node* o) {
Node* son=null;
while(o!=null) {
splay(o);
o->ch[]=son;
o->maintain();
son=o; o=o->fa;
}
}
void evert(Node* o) {
Access(o);
splay(o);
o->reverse();
}
/*
void Link(Node *u,Node *v) {
evert(u);
u->fa=v;
}
void Cut(Node *u,Node *v) {
evert(u);
Access(v); splay(v);
u->fa=v->ch[0]=null;
v->maintain();
}
*/
void Link(Node* u,Node* v) { //改变父亲为v 需要切断原来的父亲
Access(u),splay(u);
u->ch[]->fa=u->ch[]=null;
u->fa=v;
} } namespace SAM { struct Snode {
Snode *ch[],*fa;
int l;
LCT::Node *lct;
Snode(int _=) :fa(0x0),l(_) {
memset(ch,,sizeof(ch));
lct=new LCT::Node;
}
} *root=new Snode,*last=root; void add(int x) {
Snode *p=last,*np=new Snode(p->l+);
last=np;
for(;p&&!p->ch[x];p=p->fa)
p->ch[x]=np;
if(!p) {
np->fa=root;
LCT::Link(np->lct,root->lct);
} else {
Snode *q=p->ch[x];
if(q->l==p->l+) {
np->fa=q;
LCT::Link(np->lct,q->lct);
} else {
Snode* nq=new Snode(p->l+);
memcpy(nq->ch,q->ch,sizeof nq->ch);
nq->fa=q->fa;
LCT::Link(nq->lct,q->fa->lct);
np->fa=nq; q->fa=nq;
LCT::Link(q->lct,nq->lct); //修改parent树中的父亲
LCT::Link(np->lct,nq->lct);
q->lct->up_push();
nq->lct->v=q->lct->v; for(;p&&p->ch[x]==q;p=p->fa)
p->ch[x]=nq;
}
}
LCT::Access(np->lct);
LCT::splay(np->lct);
np->lct->addv();
}
void insert(char *s) {
for(int i=;s[i];i++)
add(s[i]-'A');
}
int query(char *s) {
for(Snode *p=root;p;p=p->ch[(*s++)-'A'])
if(!*s) return p->lct->up_push(),p->lct->v;
return ;
} } void Decode(char s[],int mask)
{
int i,n=strlen(s);
for(int i=;i<n;i++) {
mask=(mask*+i)%n;
swap(s[i],s[mask]);
}
} int q,mask;
char s[N],op[]; int main()
{
scanf("%d%s",&q,s);
SAM::insert(s);
while(q--) {
scanf("%s%s",op,s);
Decode(s,mask);
if(op[]=='Q') {
int ans=SAM::query(s);
mask^=ans;
printf("%d\n",ans);
} else {
SAM::insert(s);
}
}
return ;
}