bzoj 2555: SubString【后缀自动机+LCT】

一直WA……找了半天错的发现居然是解密那里的mask其实是不能动的……传进去的会变，但是真实的那个不会变……

然后就是后缀自动机，用LCT维护parent树了……注意不能makeroot，因为自动机的根是不会变的（同理也不能翻转区间），其实就是低配LCT（？）

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=3000005;

int q,n,m,fa[N],ch[N][27],dis[N],la,cur=1,con=1,ma,st[N],top;

char o[10],s[N];

struct qwe

{

	int c[2],f,s,lz;

}t[N<<1];

bool srt(int x)

{

	return t[t[x].f].c[0]!=x&&t[t[x].f].c[1]!=x;

}

void ud(int x,int y)

{

	if(x)

		t[x].s+=y,t[x].lz+=y;

}

void pd(int x)

{

	if(t[x].lz)

	{

		ud(t[x].c[0],t[x].lz);

		ud(t[x].c[1],t[x].lz);

		t[x].lz=0;

	}

}

void zhuan(int x)

{

	int y=t[x].f,z=t[y].f,l=(t[y].c[0]!=x),r=l^1;

	if(!srt(y))

		t[z].c[t[z].c[0]!=y]=x;

	t[x].f=z;

	t[t[x].c[r]].f=y,t[y].c[l]=t[x].c[r];

	t[x].c[r]=y,t[y].f=x;

}

void splay(int x)

{

	top=0;

	st[++top]=x;

	for(int i=x;!srt(i);i=t[i].f)

		st[++top]=t[i].f;

	for(int i=top;i>=1;i--)

		pd(st[i]);

	while(!srt(x))

	{

		int y=t[x].f,z=t[y].f;

		if(!srt(y))

			((t[y].c[0]==x)^(t[z].c[0]==y))?zhuan(x):zhuan(y);

		zhuan(x);

	}

}

void acc(int x)

{

	for(int i=0;x;i=x,x=t[x].f)

	{

		splay(x);

		t[x].c[1]=i;

	}

}

void lk(int x,int y)

{

	t[x].f=y;

	acc(y);

	splay(y);

	ud(y,t[x].s);

}

void ct(int x)

{

	acc(x);

	splay(x);

	ud(t[x].c[0],-t[x].s);

	t[t[x].c[0]].f=0,t[x].c[0]=0;

}

void ins(int c)

{

	la=cur,dis[cur=++con]=dis[la]+1,t[cur].s=1;

	int p=la;

	for(;p&&!ch[p][c];p=fa[p])

		ch[p][c]=cur;

	if(!p)

		fa[cur]=1,lk(cur,1);

	else

	{

		int q=ch[p][c];

		if(dis[q]==dis[p]+1)

			fa[cur]=q,lk(cur,q);

		else

		{

			int nq=++con;

			dis[nq]=dis[p]+1;

			memcpy(ch[nq],ch[q],sizeof(ch[q]));

			fa[nq]=fa[q];

			lk(nq,fa[q]);

			fa[q]=fa[cur]=nq;

			ct(q),lk(q,nq),lk(cur,nq);

			for(;ch[p][c]==q;p=fa[p])

				ch[p][c]=nq;

		}

	}

}

int ques(int len)

{

	int nw=1;

	for(int i=0;i<len;i++)

		if(!(nw=ch[nw][s[i]-'A']))

			return 0;

	splay(nw);

	return t[nw].s;

}

int main()

{

	scanf("%d%s",&q,s+1);

	n=strlen(s+1);

	for(int i=1;i<=n;i++)

		ins(s[i]-'A');

	while(q--)

	{

		scanf("%s%s",o+1,s);

		m=strlen(s);

		for(int i=0,re=ma;i<m;i++)

		{

			re=(re*131+i)%m;

			swap(s[i],s[re]);

		}

		if(o[1]=='Q')

		{

			int ans=ques(m);

			printf("%d\n",ans);

			ma^=ans;

		}

		else

		{

			for(int i=0;i<m;i++)

				ins(s[i]-'A');

		}

	}

	return 0;

}

巴特西

bzoj 2555: SubString【后缀自动机+LCT】

最新文章

热门文章