洛谷 P5212 SubString【SAM+LCT】

传送门
如果这题可以离线的话当然就SAM+线段树合并了，但是它居然来了个强制在线，给了个神奇的解码函数，我没有注意mask是传的参数，交上去直接WA，怀疑人生。
当然这题要强制在线的话就用LCT来维护parent树，维护子树和就行了，LCT的link和cut与sam里fa指针的动作保持一致就很好维护了。
当然询问的时候可以先断开p与fa[p]的链接，然后将p设为根，查p的子树和就ok，然后再连接p和fa[p]。
不知道为什么不开O2直接超时，开了O2速度能跑进第一页……可能是因为makeroot操作有点多余吧，我看题解有说没有必要makeroot的，但是我有点没想明白为什么，而且我不makeroot还会错。

#include <bits/stdc++.h>
using namespace std;
const int N=4e6+10;

struct LCT{
	int fa[N*2],ch[N*2][2],f[N*2],f2[N*2],rev[N*2],val[N*2];
	#define ls(x) (ch[x][0])
	#define rs(x) (ch[x][1])
	#define ident(p,f) (ch[f][1]==p)
	#define connect(p,f,k) (ch[fa[p]=f][k]=p)
	#define ntroot(p) (ls(fa[p])==p||rs(fa[p])==p)
	inline void pushup(int p) {f[p]=f[rs(p)]+f[ls(p)]+val[p]+f2[p];}
	inline void Rev(int p){swap(ls(p),rs(p));rev[p]^=1;}
	inline void pushdw(int p){if(rev[p]) Rev(ls(p)),Rev(rs(p));rev[p]=0;}
	inline void rotate(int p){
		int f=fa[p],ff=fa[f],k=ident(p,f);
		connect(ch[p][k^1],f,k);
		fa[p]=ff;
		if(ntroot(f)) ch[ff][ident(f,ff)]=p;
		connect(f,p,k^1);
		pushup(f),pushup(p);
	}
	inline void pushall(int p){if(ntroot(p)) pushall(fa[p]);pushdw(p);}
	inline void splay(int p){
		pushall(p);
		while(ntroot(p)){
			int f=fa[p],ff=fa[f];
			if(ntroot(f)) ident(p,f)^ident(f,ff)?rotate(p):rotate(f);
			rotate(p);
		}
	}
	void access(int p){
		for(int t=0;p;p=fa[t=p])
			splay(p),f2[p]+=f[rs(p)]-f[t],
			rs(p)=t,pushup(p);
	}
	void makert(int p){
		access(p);splay(p);Rev(p);
	}
	int findrt(int p){
		access(p);splay(p);
		while(ls(p)) p=ls(p),pushdw(p);
		splay(p);return p;
	}
	void split(int p,int q){
		makert(p);access(q);splay(q);
	}
	void link(int p,int q){
		makert(p);makert(q);fa[p]=q;
		f2[q]+=f[p];pushup(q);
	}
	void cut(int p,int q){
		split(p,q);fa[p]=ls(q)=0;pushup(q);
	}
}lct;

int n,m,mask;
char s[N];

struct SuffixAutomaton{
	int last=1,tot=1,fa[N*2],len[N*2],ch[N*2][2];
	int newnode(int x){fa[++tot]=fa[x];len[tot]=len[x];memcpy(ch[tot],ch[x],sizeof(ch[tot]));return tot;}
	void append(int c){
		int p=last,np=last=newnode(0);
		len[np]=len[p]+1; lct.val[np]=1;
		for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
		if(!p) fa[np]=1;
		else if(len[ch[p][c]]==len[p]+1) fa[np]=ch[p][c];
		else{
			int q=ch[p][c],nq=newnode(q);len[nq]=len[p]+1;
			lct.cut(q,fa[q]);
			lct.link(nq,fa[q]);
			fa[q]=fa[np]=nq;
			lct.link(q,nq);
			for(;p&&ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
		}
		lct.link(np,fa[np]);
	}
	int ask(){
		int p=1,flag=1;
		for(int i=0;i<n;i++)
			if(ch[p][s[i]-‘A‘]) p=ch[p][s[i]-‘A‘];
			else {flag=0;break;}
		if(!flag) return 0;
		lct.cut(p,fa[p]);
		lct.splay(p);
		int res=lct.f[p];
		lct.link(p,fa[p]);
		return res;
	}
}sam;

void decode(int mask){
	for(int i=0;i<n;i++){
		mask=(mask*131+i)%n;
		swap(s[i],s[mask]);
	}
}

int main(){
	scanf("%d",&m);
	scanf("%s",s);
	n=strlen(s);
	for(int i=0;i<n;i++) sam.append(s[i]-‘A‘);
	while(m--){
		char opt[10];
		scanf("%s%s",opt,s);
		n=strlen(s);decode(mask);
		if(opt[0]==‘A‘){
			for(int i=0;i<n;i++) sam.append(s[i]-‘A‘);
		}
		else{
			int res=sam.ask();
			printf("%d\n",res);
			mask^=res;
		}
	}
	return 0;
}

洛谷 P5212 SubString【SAM+LCT】

原文：https://www.cnblogs.com/BakaCirno/p/12718446.html