做到这题，发现自己对\(SAM\)的一些性质还不知道，特此记录。
题目要求01字符串区间内前缀的最长公共后缀
由SAM parent tree性质可知，2个前缀的最长公共后缀就是它们在parent tree上lca的len值
如何去感性理解
我们知道，在parent tree上每个节点都代表了一个endpos等价类，由后缀链接将他们连接起来，并且从根顺着向上走其实是一个不断从开头删去字符的过程，佐张图以供理解：
如果我们将一个前缀不停删去它的前缀（其实就是跳它的后缀）的过程看作是在parent tree上向根跳跃，并在所经历的节点上打上标记，那么，当另一个前缀也重复上述过程时，碰到的第一个有标记的节点的len，即为两前缀的最长公共后缀
前缀最长公共前缀解决了，现在我们想想如何维护这个跳后缀的过程。
发现这其实是一个根到目标节点的链覆盖，发现重链剖分并不能很好维护标记。
考虑实链剖分，联想到LCT的access操作：将根到u的路径变为一条实链。
正是我们需要的链覆盖（可脑补一下过程
LCT上只需要维护一下颜色覆盖和标记即可（根不变甚至不需要反转，pushup，link，cut
现在我们还有最后一个棘手的要求：区间
既然可以离线，考虑扫描线，将询问挂在右端点上。
先将SAM建好，明确parent tree的形态，从左至右加入前缀。
每次access时查看最近一次访问此节点的标记，并以此标记（不是自己），在任意一个可维护区间最大值的数据结构上更新区间后缀最大值。
然后贪心的覆盖上自己的标。
查询即在处理完R后询问维护的 \(L-N\) 的后缀最大值即可。
关于为什么直接覆盖，可以想到，每次是查询区间后缀最大值，端点越靠右，能影响更新到的区间就越多。
代码细节实现如下：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
inline int rd(void){
char ch=getchar();int f=1,res=0;
while(!isdigit(ch)){
if(ch=='-')f=0;
ch=getchar();
}
while(isdigit(ch)){
res=res*10+(ch-'0');
ch=getchar();
}
return f?res:-res;
}
const int N=4e5+10;
int ch[N][2],links[N],len[N],tot=1,pos[N];
int last=1,tr[N][2],n,m;
void sam_extend(int x,int id){
int cur=++tot;
len[cur]=len[last]+1;
pos[id]=tot;
int p=last;
while(p&&tr[p][x]==0){
tr[p][x]=cur;
p=links[p];
}
if(p==0){
links[cur]=1;
}else{
int q=tr[p][x];
if(len[p]+1==len[q]){
links[cur]=q;
}
else{
int cl=++tot;
memcpy(tr[cl],tr[q],sizeof(tr[q]));
links[cl]=links[q];
len[cl]=len[p]+1;
while(p&&tr[p][x]==q){
tr[p][x]=cl;
p=links[p];
}
links[q]=links[cur]=cl;
}
}
last=cur;
}
int f[N];
struct BIT{
int t[N];
inline int lowbit(int x){return x&(-x);}
void upd(int x,int v){
x=n-x+1;
while(x<=n){
t[x]=max(t[x],v);
x+=lowbit(x);
}
}
inline int query(int x){
int res=0;
x=n-x+1;
while(x){
res=max(res,t[x]);
x-=lowbit(x);
}
return res;
}
}bit;
inline int nrt(int x){
return (ch[f[x]][0]==x||ch[f[x]][1]==x);
}
inline int son(int x){
return x==ch[f[x]][1];
}
void rotate(int x){
int y=f[x],z=f[y];
int kx=son(x),ky=son(y),w=ch[x][kx^1];
if(nrt(y))ch[z][ky]=x;
ch[x][kx^1]=y;
ch[y][kx]=w;
f[x]=z;f[y]=x;
if(w)f[w]=y;
}
int tg[N],col[N];
void change(int x,int v){
tg[x]=col[x]=v;
}
void pd(int x){
if(!tg[x])return ;
if(ch[x][0])change(ch[x][0],tg[x]);
if(ch[x][1])change(ch[x][1],tg[x]);
tg[x]=0;
}
int sta[N];
void splay(int x){
int now=x,top=0;
sta[++top]=x;
while(nrt(now))sta[++top]=now=f[now];
while(top)pd(sta[top--]);
while(nrt(x)){
int y=f[x],z=f[y];
if(nrt(y))
(son(y)^son(x))?rotate(x):rotate(y);
rotate(x);
}
}
void access(int x,int v){
int pre;
for(pre=0;x;x=f[pre=x]){
splay(x);
bit.upd(col[x],len[x]);
ch[x][1]=pre;
}
splay(pre);
change(pre,v);
}
char s[N];
int ans[N];
#define pii pair<int,int>
vector<pii> G[N];
int main(){
n=rd();m=rd();scanf("%s",s+1);
for(int i=1;i<=n;i++)sam_extend(s[i]-'0',i);
for(int i=1,l,r;i<=m;i++){
l=rd();r=rd();
G[r].push_back({l,i});
}
for(int i=2;i<=tot;i++){
f[i]=links[i];
//printf("* %d\n",len[i]);
//printf("%d %d\n",links[i],i);
}
for(int i=1;i<=n;i++){
access(pos[i],i);
for(pii j:G[i]){
ans[j.second]=bit.query(j.first);
}
}
for(int i=1;i<=m;i++){
printf("%d\n",ans[i]);
}
return 0;
}