【BZOJ2555】SubString

  其实就是维护由SAM中的link边构成的树。

  每次新增一条link就用一个LCT维护一下就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=600010;

struct SAM
{
	struct LCT
	{
		struct Node
		{
			Node *c[2],*p,*lcp;
			int v;
			int tag;
			int w() {return p->c[1]==this;}
		}MEM[maxn<<1],*ID[maxn<<1],*Null;

		int cnt;
		#define ls (x->c[0])
		#define rs (x->c[1])

		Node* NewNode(int _v=0)
		{
			++cnt;
			MEM[cnt].c[0]=MEM[cnt].c[1]=MEM[cnt].p=MEM[cnt].lcp=Null;
			MEM[cnt].v=_v;
			MEM[cnt].tag=0;
			return &MEM[cnt];
		}

		LCT()
		{
			Null=&MEM[0];
			Null->c[0]=Null->c[1]=Null->p=Null->lcp=Null;
			Null->v=Null->tag=0;
		}

		void Mark_Add(Node *x,int v) {if (x==Null) return;x->v+=v;x->tag+=v;}

		void Push_Down(Node *x)
		{
			if (x->tag)
			{
				Mark_Add(ls,x->tag);
				Mark_Add(rs,x->tag);
				x->tag=0;
			}
		}

		void Rotate(Node *x)
		{
			Node *p=x->p;
			int w=x->w();
			x->lcp=p->lcp;p->lcp=Null;
			Push_Down(p);Push_Down(x);
			x->p=p->p;p->p->c[p->w()]=x;
			x->c[!w]->p=p;p->c[w]=x->c[!w];
			x->c[!w]=p;p->p=x;
		}

		void Splay(Node *x)
		{
			Push_Down(x);
			while (x->p!=Null)
			{
				if (x->p->p==Null) {Rotate(x);break;}
				if (x->w()==x->p->w()) Rotate(x->p),Rotate(x);
				else Rotate(x),Rotate(x);
			}
		}

		void Access(Node *x)
		{
			Node *v=Null,*pre=x;
			while (x!=Null)
			{
				Splay(x);
				rs->p=v->lcp=Null;
				rs->lcp=v->p=x;
				rs=v;
				v=x;x=x->lcp;
			}
			Splay(pre);
		}
		
		void Add_Node(int x,int c)
		{
			ID[x]=NewNode(c);
		}

		void Link(int x,int y)
		{
			ID[x]->lcp=ID[y];
			Access(ID[y]);
			Mark_Add(ID[y],ID[x]->v);
		}
		
		void Cut(int x)
		{
			Access(ID[x]);
			ID[x]->c[0]->p=Null;
			Mark_Add(ID[x]->c[0],-ID[x]->v);
			ID[x]->c[0]=Null;
		}

		int Query(int x)
		{
			Access(ID[x]);
			return ID[x]->v;
		}
	}T;

	struct State
	{
		int next[26];
		int link;
		int len;
	}st[maxn<<1];

	int cnt,last;

	SAM() {cnt=last=1;T.ID[1]=T.NewNode();}

	void Extend(int c)
	{
		int x=++cnt,p;
		T.Add_Node(x,1);
		st[x].len=st[last].len+1;
		for (p=last;p && !st[p].next[c];p=st[p].link) st[p].next[c]=x;
		if (!p) st[x].link=1,T.Link(x,1);
		else {
			int q=st[p].next[c];
			if (st[p].len+1==st[q].len) st[x].link=q,T.Link(x,q);
			else {
				int v=++cnt;
				T.Add_Node(v,0);
				st[v]=st[q];
				st[v].len=st[p].len+1;
				T.Cut(q);T.Link(v,st[v].link);
				for (;p && st[p].next[c]==q;p=st[p].link) st[p].next[c]=v;
				st[x].link=st[q].link=v;
				T.Link(x,v);T.Link(q,v);
			}
		}
		last=x;
	}

	void Insert(char *ch)
	{
		int n=strlen(ch);
		for (int i=0;i<n;i++) Extend(ch[i]-'A');
	}

	int Query(char *ch)
	{
		int n=strlen(ch),x=1;
		for (int i=0;i<n;i++)
		{
			int c=ch[i]-'A';
			if (!st[x].next[c]) return 0;
			x=st[x].next[c];
		}
		return T.Query(x);
	}
}M;

void decodeWithMask(char *ch,int mask)
{
	int n=strlen(ch);
	for (int j=0;j<n;j++)
		swap(ch[j],ch[mask=((mask*131)+j)%n]);
}

char ch[maxn],type[10];
int q,mask,ans;

int main()
{
	scanf("%d",&q);
	scanf("%s",ch);
	M.Insert(ch);
	for (int i=1;i<=q;i++)
	{
		scanf("%s%s",type,ch);
		decodeWithMask(ch,mask);
		if (type[0]=='A') M.Insert(ch);
		else printf("%d\n",ans=M.Query(ch)),mask^=ans;
	}
	return 0;
}