BZOJ 2555 SubString（LCT+后缀树）

喜闻乐见的LCT+SAM

此题要求动态插入，直接上后缀树。然后询问其实就是求一个节点的子树后缀结束节点的个数。

因为建立后缀树需要插入和删除，就直接上LCT。每次加入一个点，把它到根的路径加一

（现在我才知道access之后那个splay就是这个点到根的路径，LCT学得不好）

思路不需要说太多，就是码量大。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

const int N=3001000;

int T,ans;

char s[N];

int read(){

	int sum=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}

	return sum*f;

}

int get(int ans){

    cin>>s;

    int len=strlen(s);

    for (int j=0;j<len;j++) {

        ans=(ans*131+j)%len;

        char c=s[j];

        s[j]=s[ans];

        s[ans]=c;

    }

    return len;

}

struct lct{

	int fa[N],ch[N][2],w[N],lazy[N],stack[N];

	void add(int x,int y){

		w[x]+=y;lazy[x]+=y;

	}

    void pushdown(int x){

		if(lazy[x]){

			add(ch[x][0],lazy[x]);add(ch[x][1],lazy[x]);

			lazy[x]=0;

		}

	}

	bool isroot(int x){

		return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;

	}

	bool son(int x){

		return ch[fa[x]][1]==x;

	}

	void rotate(int x){

		int y=fa[x],z=fa[y],a=son(x),b=son(y),c=ch[x][!a];

		if(!isroot(y))ch[z][b]=x;fa[x]=z;

		if(c)fa[c]=y;ch[y][a]=c;

		ch[x][!a]=y;fa[y]=x;

	}

	void splay(int x){

		int top=1,a=x;stack[top]=a;

		while(a)stack[++top]=a=fa[a];

		while(top)pushdown(stack[top--]);

		while(!isroot(x)){

			int y=fa[x],z=fa[y];

			if(isroot(y))rotate(x);

			else{

				if(son(x)==son(y))rotate(y);

				else rotate(x);

				rotate(x);

			}

		}

	}

	void access(int x){

		for(int j=0;x;j=x,x=fa[x])

			splay(x),ch[x][1]=j;

	}

	void link(int x,int f){

		fa[x]=f;access(f);splay(f);add(f,w[x]);

	}

	void cut(int x){

		access(x);splay(x);add(ch[x][0],-w[x]);

		fa[ch[x][0]]=0;ch[x][0]=0;

	}

}t;

struct SAM{

	int tot,u,ln[N],size[N],trans[N][27],fa[N];

	void ins(int c){

		int x=++tot;ln[x]=ln[u]+1;size[x]=1;

		t.w[x]=1;

		for(;u&&trans[u][c]==0;u=fa[u])trans[u][c]=x;

		if(u==0)fa[x]=1,t.link(x,1);

		else{

			int v=trans[u][c];

			if(ln[v]==ln[u]+1)fa[x]=v,t.link(x,v);

			else{

				int w=++tot;

				ln[w]=ln[u]+1;fa[w]=fa[v];

				t.link(w,fa[w]);

				memcpy(trans[w],trans[v],sizeof(trans[w]));

				fa[x]=fa[v]=w;

				t.cut(v);t.link(v,w);t.link(x,w);

				for(;u&&trans[u][c]==v;u=fa[u])trans[u][c]=w;

			}

		}

		u=x;

	}

	void add(){

		int len=get(ans);

		for(int i=0;i<len;i++)ins(s[i]-'A'+1);

	}

	int check(){

		int len=get(ans);

		int now=1;

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

			if(trans[now][s[i]-'A'+1]==0)return 0;

			now=trans[now][s[i]-'A'+1];

		}

		t.splay(now);

		return t.w[now];

	}

}sam;

int main(){

	T=read();

	sam.tot=sam.u=1;

	cin>>s;

	int len=strlen(s);

	for(int i=0;i<len;i++)sam.ins(s[i]-'A'+1);

	while(T--){

		cin>>s;

		if(s[0]=='Q'){

			int tmp=sam.check();

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

			ans^=tmp;

		}

		else sam.add();

	}

	return 0;

}

巴特西

BZOJ 2555 SubString（LCT+后缀树）

最新文章

热门文章