Qwen 神力回滚莫队 + ST 表侥幸卡过本题。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,inf=1e9;
char str[N];
int sa[N],rk[N*2],lst[N*2],P,h[N],n,m,B;
bool cmp(int x,int y){return rk[x]!=rk[y]?rk[x]<rk[y]:rk[x+P]<rk[y+P];}
int st[N][21];
void build()
{
	for(int i=1;i<=n;i++)sa[i]=i,rk[i]=str[i];
	for(P=1;P<n;P<<=1)
	{
		sort(sa+1,sa+n+1,cmp);
		for(int i=1;i<=n;i++)lst[i]=rk[i];
		for(int i=1,cnt=0;i<=n;i++)
		{
			if(lst[sa[i]]==lst[sa[i-1]]&&lst[sa[i]+P]==lst[sa[i-1]+P])
				rk[sa[i]]=cnt;
			else rk[sa[i]]=++cnt;
		}
	}
	for(int i=1,k=0;i<=n;i++)
	{
		if(rk[i]==0)continue;
		if(k)k--;
		while(str[i+k]==str[sa[rk[i]-1]+k])k++;
		h[rk[i]]=k;
	}
	for(int i=1;i<=n;i++)st[i][0]=h[i];
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
			st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
int get(int l,int r)
{
	if(l==0||r==0||l>n||r>n)return 0;
	if(l==r)return n-sa[l]+1;
	if(l>r)swap(l,r);
	l++;int k=__lg(r-l+1);
	return min(st[l][k],st[r-(1<<k)+1][k]);
}
struct node{int l,r,id,b;}q[N];
bool cmp1(node n1,node n2){return n1.b!=n2.b?n1.b<n2.b:n1.r<n2.r;}
int ans[N],tmp[N];
signed main()
{
	cin>>n>>m>>(str+1);B=max(1,(int)(n/sqrt(m)));
	reverse(str+1,str+n+1);
	build();
	for(int i=1;i<=m;i++)
	{
		cin>>q[i].l>>q[i].r;q[i].id=i;
		q[i].l=n-q[i].l+1;
		q[i].r=n-q[i].r+1;
		swap(q[i].l,q[i].r);
		q[i].b=(q[i].l-1)/B+1;
	}
	sort(q+1,q+m+1,cmp1);
	for(int i=1;i<=m;)
	{
		int p=i,br=min(n,q[i].b*B);
		set<int>s;
		int mx=0,mr=br;
		while(p<=m&&q[p].b==q[i].b)
		{
			if(q[p].r<=br)
			{
				int len=0;
				for(int j=q[p].l;j<=q[p].r;j++)tmp[++len]=rk[j];
				sort(tmp+1,tmp+len+1);
				int mx1=0;
				for(int j=1;j<len;j++)mx1=max(mx1,get(tmp[j],tmp[j+1]));
				ans[q[p].id]=mx1;
				p++;
				continue;
			}
			while(mr<q[p].r)
			{
				mr++;int x=rk[mr];
				auto it=s.insert(x).first;
				int pl=0,pr=0;
				if(it!=s.begin())pl=*prev(it);
				if(next(it)!=s.end())pr=*next(it);
				if(pl)mx=max(mx,get(pl,x));
				if(pr)mx=max(mx,get(x,pr));
			}
			int lstans=mx,len=0;
			for(int j=br;j>=q[p].l;j--)tmp[++len]=rk[j];
			sort(tmp+1,tmp+len+1);tmp[0]=0,tmp[len+1]=inf;
			for(int j=1;j<=len;j++)
			{
				int x=tmp[j],pl=tmp[j-1],pr=tmp[j+1];
				auto it=s.lower_bound(x);
				if(it!=s.begin())pl=max(pl,*prev(it));
				if(it!=s.end())pr=min(pr,*it);
				if(pl)mx=max(mx,get(pl,x));
				if(pr!=inf)mx=max(mx,get(x,pr));
			}
			ans[q[p].id]=mx;
			mx=lstans;
			p++;
		}
		i=p;
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
	return 0;
}

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define Gmax(x,y) (x<(y)&&(x=(y)))
#define swap(x,y) (x^=y^=x^=y)
#define pb(x,y) (nxt[y]=lnk[x],lnk[x]=y) 
using namespace std;
int n,m,a[N+5],q[N+5],lnk[N+5],nxt[N+5],ans[N+5];
class FastIO
{
	private:
		#define FS 100000
		#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)
		#define pc(c) (C^FS?FO[C++]=c:(fwrite(FO,1,C,stdout),FO[(C=0)++]=c))
		#define tn (x<<3)+(x<<1)
		#define D isdigit(c=tc())
		int T,C;char c,*A,*B,FI[FS],FO[FS],S[FS];
	public:
		I FastIO() {A=B=FI;}
		Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);}
		Tp I void write(Ty x) {W(S[++T]=x%10+48,x/=10);W(T) pc(S[T--]);}
		Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
		Tp I void writeln(Con Ty& x) {write(x),pc('\n');}
		I void readbit(int& x) {W(!D);x=c&1;}
		I void clear() {fwrite(FO,1,C,stdout),C=0;}
}F;
template<int SZ> class SuffixAutomation//后缀自动机
{
	private:
		int lst;struct Trie {int L,F,S[2];}O[SZ<<1];
	public:
		int tot,l[SZ<<1],f[SZ<<1];I SuffixAutomation() {tot=lst=1;}
		I void Record() {for(RI i=1;i<=tot;++i) l[i]=O[i].L,f[i]=O[i].F;}
		I int Insert(CI x)//插入节点
		{
			RI p=lst,q,k,now=lst=++tot;O[now].L=O[p].L+1;
			W(p&&!O[p].S[x]) O[p].S[x]=now,p=O[p].F;if(!p) return O[now].F=1,now;
			if(O[p].L+1==O[q=O[p].S[x]].L) return O[now].F=q,now;
			O[k=++tot]=O[q],O[k].L=O[p].L+1,O[now].F=O[q].F=k;
			W(p&&!(O[p].S[x]^q)) O[p].S[x]=k,p=O[p].F;return now;
		}
};
template<int SZ> class TreeArray//树状数组
{
	private:
		#define lowbit(x) ((x)&-(x))
		int a[SZ+5];
	public:
		I void Add(RI x,CI v) {W(x) Gmax(a[x],v),x-=lowbit(x);}//单点修改
		I int Qry(RI x) {RI t=0;W(x<=n) Gmax(t,a[x]),x+=lowbit(x);return t;}//区间询问
};
class LinkCutTree//LCT
{
	private:
		#define Upt(x,v) (O[x].f=O[x].V=v)
		#define PD(x) (O[x].f&&(Upt(O[x].S[0],O[x].f),Upt(O[x].S[1],O[x].f),O[x].f=0))
		#define IR(x) (O[O[x].F].S[0]^x&&O[O[x].F].S[1]^x)
		#define Wh(x) (O[O[x].F].S[1]==x)
		#define Co(x,y,d) (O[O[x].F=y].S[d]=x)
		static Con int SZ=N<<1;int p[SZ+5],St[SZ+5];struct node {int f,V,F,S[2];}O[SZ+5];
		SuffixAutomation<N> SAM;TreeArray<N<<1> T;
		I void Ro(CI x)
		{
			RI f=O[x].F,p=O[f].F,d=Wh(x);!IR(f)&&(O[p].S[Wh(f)]=x);
			O[x].F=p,Co(O[x].S[d^1],f,d),Co(f,x,d^1);
		}
		I void S(CI x)
		{
			RI f=x,T=0;W(St[++T]=f,!IR(f)) f=O[f].F;W(T) PD(St[T]),--T;
			W(!IR(x)) f=O[x].F,!IR(f)&&(Ro(Wh(x)^Wh(f)?x:f),0),Ro(x);
		}
	public:
		I void Init(CI x,int* v) 
		{
			RI i;for(i=1;i<=n;++i) p[i]=SAM.Insert(v[i]);SAM.Record();
			for(i=1;i<=SAM.tot;++i) O[i].F=SAM.f[i];
		}
		I void Ac(RI x,CI v)//Access求LCA的过程，注意更新节点信息与答案
		{
			RI s;for(x=p[x],s=0;x;x=O[s=x].F) S(x),
				T.Add(O[x].V,SAM.l[x]),O[x].S[1]=s;Upt(s,v);
		}
		I int Query(CI x) {return T.Qry(x);}//询问答案
}LCT;
int main()
{
	RI Qtot,i,j,x;for(F.read(n,Qtot),i=1;i<=n;++i) F.readbit(a[i]);
	for(LCT.Init(n,a),i=1;i<=Qtot;++i) F.read(q[i],x),pb(x,i);//离线用邻接表存储
	for(i=1;i<=n;++i) for(LCT.Ac(i,i),j=lnk[i];j;j=nxt[j]) ans[j]=LCT.Query(q[j]);//枚举右端点，更新信息并处理询问
	for(i=1;i<=Qtot;++i) F.writeln(ans[i]);return F.clear(),0;//输出答案
}