【雅礼集训 2017 Day7】【SAM】【LCT】【SGT】事情的相似度

【描述】
人的一生不仅要靠自我奋斗，还要考虑到历史的行程。
历史的行程可以抽象成一个 01 串，作为一个年纪比较大的人，你希望从历史的行程中获得一些姿势。
你发现在历史的不同时刻，不断的有相同的事情发生。比如，有两个人同时在世纪之交 11 年的时候上台，同样喜欢与洋人谈笑风生，同样提出了以「三」字开头的理论。
你发现，一件事情可以看成是这个 01 串的一个前缀，这个前缀最右边的位置就是这个事情的结束时间。
两件事情的相似度可以看成，这两个前缀的最长公共后缀长度。
现在你很好奇，在一段区间内结束的事情中最相似的两件事情的相似度是多少呢？
【输入】
第一行两个整数 n、m，表示串长和询问个数。
第二行长度为 n 的 01 串，表示历史的行程。
接下来 m 行，每行两个正整数 l 、r 表示询问的区间，包括端点，保证 1≤l<e≤n
【输出】
输出 m 行，对每个询问输出一个整数表示最大的相似度

【思路】

这道题其实挺套路的。我们考虑每个点对的贡献。但是点对有$O(n^2)$O(n2)个，仔细分析一下就会发现，对于如图所示的三个点对，如果它们的贡献都是len，那么其实我们只需要考虑点对(C,D)即可了，因为如果有区间包含点对(A,D)(B,D)，就一定包含点对(C,D)，这样点对数量就大大减小。这个性质是这道题两种做法的基础。
我们考虑维护一个SAM，每次加入一个后缀C后，暴力地跳fail链，找到上一个经过当前点的后缀B的位置，那么上一个位置的后缀B和这个位置的后缀C就是一个可能对答案有贡献的点对。我们将询问按右端点排序，用线段树或树状数组维护答案。设下一个经过这里的后缀为D，那么显然（B,D）已经不会产生贡献，所以我们把当前点上一个出现的位置更新为C。由于我们对于之前的后缀和当前后缀的贡献只有相交的深度最深的那个点才可能产生贡献，所以暴力跳fail链的过程可以用LCT维护，这就是一个access。同一棵splay维护上一个经过该点的后缀位置相同的一条链，同一棵splay更新答案只需要最深的那个点即可。这样复杂度就有了保证。线段树(树状数组)支持单点修改，后缀max。
代码：

#include<bits/stdc++.h>
#define re register
using namespace std;
const int N=2e5+5;
typedef long long ll;
inline int red(){
    int re data=0;bool w=0; char ch=getchar();
    while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
    if(ch=='-') w=1,ch=getchar();
    while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar();
    return w?-data:data;
}
int n,m;
char s[N];
namespace sgt{
	#define lc (p<<1)
	#define rc (p<<1|1)
	int mx[N<<2|1];
	inline void cmax(int&x,const int&y){(x<y)&&(x=y);}
	inline void pushup(const int&p){mx[p]=max(mx[lc],mx[rc]);}
	void change(int p,int l,int r,int pos,int v){
		if(l==r)return cmax(mx[p],v);
		int mid=(l+r)>>1;
		if(pos<=mid)change(lc,l,mid,pos,v);
		else change(rc,mid+1,r,pos,v);
		pushup(p);
	}
	int query(int p,int l,int r,int ql,int qr){
		if(ql<=l&&qr>=r)return mx[p];
		int mid=(l+r)>>1,ans=0;
		if(ql<=mid)cmax(ans,query(lc,l,mid,ql,qr));
		if(qr>mid)cmax(ans,query(rc,mid+1,r,ql,qr));
		return ans;
	}
}
namespace LCT{
	int fa[N],tag[N],col[N],ch[N][2],s[N],top=0,len[N];
	inline bool isroot(int x){return x!=ch[fa[x]][1]&&x!=ch[fa[x]][0];}
	inline bool get(int x){return x==ch[fa[x]][1];}
	inline void rotate(int x){
		int y=fa[x],z=fa[y],d=get(x);
		if(!isroot(y))ch[z][get(y)]=x;
		fa[x]=z;fa[y]=x;ch[y][d]=ch[x][d^1];
		if(ch[y][d])fa[ch[y][d]]=y;
		ch[x][d^1]=y;
	}
	inline void pushnow(int x,int c){if(!x)return;col[x]=c;tag[x]=c;}
	inline void pushdown(int x){
		if(tag[x]){
			pushnow(ch[x][0],tag[x]);
			pushnow(ch[x][1],tag[x]);
			tag[x]=0;
		}
	}
	inline void splay(int x){
		s[top=1]=x;
		for(int re i=x;!isroot(i);i=fa[i])s[++top]=fa[i];
		while(top)pushdown(s[top--]);
		for(int re y=fa[x];!isroot(x);rotate(x),y=fa[x])
			if(!isroot(y))rotate(get(x)==get(y)?y:x);
	}
	inline void access(int x,int c){
		int y;
		for(y=0;x;x=fa[y=x]){
			splay(x),ch[x][1]=y;
			if(col[x])sgt::change(1,1,n,col[x],len[x]);
		}pushnow(y,c);
	}
	inline int getcol(int x){splay(x);return col[x];}
	inline void link(int x,int y){splay(x);fa[x]=y;}
}
namespace SAM{
	int ch[N][2],len[N],link[N];
	int sz=1,last=1;
	inline void insert(int c,int id){
		int cur=++sz,p=last;
		len[cur]=len[p]+1;last=cur;
		LCT::len[cur]=len[cur];
		for(;p&&!ch[p][c];p=link[p])ch[p][c]=cur;
		if(!p)return LCT::link(cur,link[cur]=1),LCT::access(cur,id);
		int q=ch[p][c];
		if(len[q]==len[p]+1)return LCT::link(cur,link[cur]=q),LCT::access(cur,id);
		int clo=++sz;len[clo]=len[p]+1;
		ch[clo][0]=ch[q][0];
		ch[clo][1]=ch[q][1];
		LCT::col[clo]=LCT::getcol(q);
		LCT::len[clo]=len[clo];
		LCT::link(clo,link[clo]=link[q]);
		LCT::link(cur,link[cur]=clo);
		LCT::access(cur,id);
		LCT::link(q,link[q]=clo);
		for(;p&&ch[p][c]==q;p=link[p])ch[p][c]=clo;
	}
}
int ans[N],l[N];
vector<int>g[N];
int main(){
	n=red();m=red();scanf("%s",s+1);
	for(int re i=1;i<=m;i++)l[i]=red(),g[red()].push_back(i);
	for(int re i=1;i<=n;i++){
		SAM::insert(s[i]-48,i);
		for(int re j=g[i].size()-1;~j;--j){
			int id=g[i][j];
			ans[id]=sgt::query(1,1,n,l[id],i);
		}
	}
	for(int re i=1;i<=m;i++)
		cout<<ans[i]<<"\n";
}