洛谷5212 BZOJ2555 SubString SAM LCT

題目連結

題意：

給出一個字元串，有兩種操作，第一個是在目前字元串後面加上一個字元串，另一個是詢問一個字元串在目前字元串中出現了多少次。總長度差不多是 1 e 6 1e6 1e6級别的。

題意：

如果隻有詢問，求一個串在原串出現的次數的話，我們就隻需要在SAM上走到詢問串末尾在SAM上對應的點，然後查詢parent樹上子樹内的結束點的個數就可以了。假如這個時候SAM上的每一個點在parent樹上的子樹結束點個數都維護好了，那麼我們考慮加入一個結束節點的影響，其實就是找到在SAM上對應的節點之後從這個點到parent樹的根的所有點的答案都要加一。那麼我們用一個LCT來維護parent樹，實作一個鍊上加一個值和單點查詢。但是由于在動态加入字元的時候SAM的parent樹形态會改變，特别是建立節點的時候，parent樹既要link也要cut，是以隻能用LCT維護。這樣就做完了。

代碼有點長，寫的時候主要是注意在建SAM的過程中怎麼更新parent樹的形态和權值就好了，其他的都是LCT和SAM的模闆。最後說明一下，空間别開得太大，在BZOJ上直接因為申請空間比較大CE了，這種CE的編譯資訊都不會給你報錯的，當時坑了我好久，因為在洛谷上都過了，然後一直CE，還隻傳回warning不傳回error，弄得我一臉懵逼。。。

代碼：

#include <bits/stdc++.h>
using namespace std;

int n,m,len[2200010],fa[2200010],ch[2200010][26],cnt=1,rt=1,lst=1;
int f[2200010],son[2200010][2],sz[2200010],del[2200010],sta[2200010];
int mask,ans;
char s[1000010],opt[10];
inline int nroot(int x)
{
	return son[f[x]][0]==x||son[f[x]][1]==x;
}
inline void pushdown(int x)
{
	if(x&&del[x])
	{
		if(son[x][0])
		{
			sz[son[x][0]]+=del[x];
			del[son[x][0]]+=del[x];
		}
		if(son[x][1])
		{
			sz[son[x][1]]+=del[x];
			del[son[x][1]]+=del[x];
		}
		del[x]=0;
	}
}
inline void rotate(int x)
{
	int y=f[x],z=f[y],k=son[y][1]==x,w=son[x][!k];
	if(nroot(y))
	son[z][son[z][1]==y]=x;
	son[x][!k]=y;
	son[y][k]=w;
	if(w)
	f[w]=y;
	f[y]=x;
	f[x]=z;
}
inline void splay(int x)
{
	int y=x,z=0;
	sta[++z]=y;
	while(nroot(y))
	{
		y=f[y];	
		sta[++z]=y;		
	}
	while(z)
	pushdown(sta[z--]);
	while(nroot(x))
	{
		y=f[x];
		z=f[y];
		if(nroot(y))
		{
			if(son[z][1]==y^son[y][1]==x)
			rotate(x);
			else
			rotate(y);
		}
		rotate(x);
	}
}
inline void access(int x)
{
	int y=0;
	while(x!=0)
	{
		splay(x);
		son[x][1]=y;
		if(y)
		f[y]=x;
		y=x;
		x=f[x];
	}
}
inline void link(int x,int y)
{
	f[y]=x;
	access(x);
	splay(x);
	sz[x]+=sz[y];
	del[x]+=sz[y];
}
inline void cut(int x,int y)
{
	access(y);
	splay(y);
	sz[x]-=sz[y];
	del[x]-=sz[y];
	son[y][0]=0;
	f[x]=0;
}
inline void insert(int x)
{
	int cur=++cnt,pre=lst;
	lst=cur;
	len[cur]=len[pre]+1;
	for(;pre&&!ch[pre][x];pre=fa[pre])
	ch[pre][x]=cur;
	if(!pre)
	{
		fa[cur]=rt;
		f[cur]=rt;
	}	
	else
	{
		int ji=ch[pre][x];
		if(len[ji]==len[pre]+1)
		{
			fa[cur]=ji;
			f[cur]=ji;
		}		
		else
		{
			int gg=++cnt;
			len[gg]=len[pre]+1;
			memcpy(ch[gg],ch[ji],sizeof(ch[ji]));		
			fa[gg]=fa[ji];
			link(fa[ji],gg);				
			for(;pre&&ch[pre][x]==ji;pre=fa[pre])
			ch[pre][x]=gg;	
			cut(fa[ji],ji);
			fa[ji]=fa[cur]=gg;		
			link(gg,ji);
			link(gg,cur);
		}
	}
	access(cur);
	splay(cur);
	++sz[cur];
	++del[cur];
}
inline void solve(int mask)
{
	for(int i=0;i<n;++i)
	{
		mask=(mask*131+i)%n;
		char t=s[i];  
        s[i]=s[mask];  
        s[mask]=t;
	}
}
inline int sam()
{
	int cur=rt;
	for(int i=0;i<n;++i)
	{
		int x=s[i]-'A';
		cur=ch[cur][x];
	}
	if(!cur)
	return 0;
	access(cur);
	splay(cur);
	return sz[cur];
}
int main()
{
	scanf("%d",&m);
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;++i)
	{
		insert(s[i]-'A');
		s[i]=0;
	}	
	mask=0;
	for(int i=1;i<=m;++i)
	{
		scanf("%s",opt+1);
		scanf("%s",s);
		n=strlen(s);
		solve(mask);
		if(opt[1]=='A')
		{
			for(int i=0;i<n;++i)
			insert(s[i]-'A');
		}
		else
		{
			ans=sam();
			printf("%d\n",ans);
			mask^=ans;
		}
		for(int i=0;i<=n;++i)
		s[i]=0;
	}
	return 0;
}