题解：后缀数组+稀疏表 对原串正反向建后缀数组并通过height数组求出本质不同字符串个数。 通过ST表预处理后可在O(1)时间内求出LCQ。
代码：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<algorithm> #include<cmath> using namespace std; typedef long long ll; const int Maxn=1e5+50; inline ll read() { char ch=getchar();ll i=0,f=1; while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){i=(i<<3)+(i<<1)+ch-'0';ch=getchar();} return i*f; } char ch[Maxn]; int n,Q,c[Maxn],Log[Maxn+500]; struct ST { int mn[Maxn][25]; int sa[Maxn],height[Maxn],rk[Maxn],m; ll s[Maxn]; inline void getsa() { m=26; int *x=rk,*y=height; for(int i=1;i<=n;i++)c[x[i]=ch[i]-'a'+1]++; for(int i=1;i<=m;i++)c[i]+=c[i-1]; for(int i=n;i>=1;i--)sa[c[x[i]]--]=i; for(int k=1;k<n;k<<=1) { int j=0; for(int i=n-k+1;i<=n;i++)y[++j]=i; for(int i=1;i<=n;i++)if(sa[i]>k)y[++j]=sa[i]-k; for(int i=1;i<=m;i++)c[i]=0; for(int i=1;i<=n;i++)c[x[i]]++; for(int i=1;i<=m;i++)c[i]+=c[i-1]; for(int i=n;i>=1;i--)sa[c[x[y[i]]]--]=y[i]; swap(x,y); j=x[sa[1]]=1; for(int i=2;i<=n;i++)x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?j:++j; if(j==n)break; m=j+1; } } inline void getheight() { for(int i=1;i<=n;i++)rk[sa[i]]=i; int k=0,j; for(int i=1;i<=n;height[rk[i++]]=k) for(k?k--:0,j=sa[rk[i]-1];ch[i+k]==ch[j+k];k++); } inline void pre() { memset(c,0,sizeof(c)); getsa(); getheight(); for(int i=1;i<=n;i++)s[i]=s[i-1]+n-sa[i]-height[i]+1; for(int i=1;i<=n;i++)mn[i][0]=height[i]; for(int i=1;i<=Log[n];i++) for(int j=1;j<=n;j++) if(j+(1<<i)-1<=n) mn[j][i]=min(mn[j][i-1],mn[j+(1<<(i-1))][i-1]); else break; } inline int query(int x1,int x2) { int r1=rk[x1],r2=rk[x2]; if(r1>r2)swap(r1,r2); r1++; int lim=Log[r2-r1+1]; return min(mn[r1][lim],mn[r2-(1<<lim)+1][lim]); } }A,B; int main() { Log[0]=-1; for(int i=1;i<Maxn;i++)Log[i]=Log[i>>1]+1; n=read(),Q=read(); scanf("%s",ch+1); A.pre(); reverse(ch+1,ch+n+1); B.pre(); while(Q--) { ll x=read(),y=read(); if(x>A.s[n]||y>A.s[n])puts("-1"); else { int id; id=lower_bound(A.s+1,A.s+n+1,x)-A.s; int l=A.sa[id]; int r=A.sa[id]+A.height[id]+x-A.s[id-1]-1; id=lower_bound(A.s+1,A.s+n+1,y)-A.s; int p=A.sa[id]; int q=A.sa[id]+A.height[id]+y-A.s[id-1]-1; ll t1=(l==p)?Maxn:A.query(l,p); ll t2=(r==q)?Maxn:B.query(n-r+1,n-q+1); t1=min(t1,(ll)min(r-l+1,q-p+1)); t2=min(t2,(ll)min(r-l+1,q-p+1)); printf("%lld\n",t1*t1+t2*t2); } } return 0; }