[BZOJ2555] SubString

bzoj

题意

给你一个初始模板串，要求资瓷以下两个操作：
1、在模板串的末尾接上一个串；
2、查询一个串在模板串中出现了多少次。
强制在线。

sol

末尾添加直接(extend)。
查询一个串的出现次数就是查对应状态的(right)集合大小。
由于是动态的所以需要用(LCT)维护。相当于是在维护子树信息（子树和）。

code

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1250000;
struct lct{
	int fa[N],ch[2][N],val[N],sum[N];
	bool son(int x)
		{
			return x==ch[1][fa[x]];
		}
	bool isroot(int x)
		{
			return x!=ch[0][fa[x]]&&x!=ch[1][fa[x]];
		}
	void pushup(int x)
		{
			sum[x]=val[x]+sum[ch[0][x]]+sum[ch[1][x]];
		}
	void rotate(int x)
		{
			int y=fa[x],z=fa[y],c=son(x);
			ch[c][y]=ch[c^1][x];if (ch[c][y]) fa[ch[c][y]]=y;
			fa[x]=z;if (!isroot(y)) ch[son(y)][z]=x;
			ch[c^1][x]=y;fa[y]=x;pushup(y);
		}
	void splay(int x)
		{
			for (int y=fa[x];!isroot(x);rotate(x),y=fa[x])
				if (!isroot(y)) son(x)^son(y)?rotate(x):rotate(y);
			pushup(x);
		}
	void access(int x)
		{
			for (int y=0;x;y=x,x=fa[x])
			{
				splay(x);val[x]+=sum[ch[1][x]]-sum[y];
				ch[1][x]=y;pushup(x);
			}
		}
	void link(int x,int y)
		{
			splay(x);access(y);splay(y);
			fa[x]=y;val[y]+=sum[x];pushup(y);
		}
	void cut(int x)
		{
			access(x);splay(x);
			ch[0][x]=fa[ch[0][x]]=0;pushup(x);
		}
}T;
int last=1,tot=1,tr[N][26],fa[N],len[N],q,mask,ans;char s[N*3],op[N];
void extend(int c)
{
	int v=last,u=++tot;T.val[last=u]=1;
	len[u]=len[v]+1;
	while (v&&!tr[v][c]) tr[v][c]=u,v=fa[v];
	if (!v) fa[u]=1,T.link(u,1);
	else{
		int x=tr[v][c];
		if (len[x]==len[v]+1) fa[u]=x,T.link(u,x);
		else{
			int y=++tot;
			memcpy(tr[y],tr[x],sizeof(tr[y]));
			if (fa[x]) T.cut(x),T.link(y,fa[x]);
			fa[y]=fa[x];fa[x]=fa[u]=y;len[y]=len[v]+1;
			T.link(x,y);T.link(u,y);
			while (v&&tr[v][c]==x) tr[v][c]=y,v=fa[v];
		}
	}
}
void decode(int l)
{
	for (int i=0,tmp=mask;i<l;++i)
		tmp=(tmp*131+i)%l,swap(s[i],s[tmp]);
}
int main()
{
	scanf("%d %s",&q,s);int l=strlen(s);
	for (int i=0;i<l;++i) extend(s[i]-'A');
	while (q--){
		scanf(" %s %s",op,s);l=strlen(s);
		decode(l);
		if (op[0]=='Q')
		{
			int now=1;
			for (int i=0;i<l;++i) now=tr[now][s[i]-'A'];
			if (!now) ans=0;
			else T.access(now),T.splay(now),ans=T.val[now];
			printf("%d
",ans);mask^=ans;
		}
		else for (int i=0;i<l;++i) extend(s[i]-'A');
	}
	return 0;
}