题目分析：
这道题我是乱搞的，因为他说$01$串是随机的。
那么我们可以猜测能够让LCP变大的地方很少。求出后缀数组之后可能让LCP变大的地方就等价于从大到小往height里动态加点同时维护这个点左右两边的单调栈。
这个事情用线段树模拟就行了。
用暴力跑一下发现果然不大，只有200w，其中很多还是废点，把废点特判一下删除掉就行了。
然后把询问离线，按r排序，再作扫描线，每次扫到r的时候把前面变动的LCP更新一下。然后对于询问也做一个类似上面单调栈的操作。
代码：
#include<bits/stdc++.h>
#define RI register
using namespace std; const int maxn = ;
const int N = ; int n,q;
char str[maxn];
int T[maxn<<],a[maxn];
int RMQ[maxn][],pw[maxn]; struct node{int l,r,nb;}qy[maxn];
int ans[maxn];
int sa[maxn],rk[maxn],X[maxn],Y[maxn];
int ht[maxn],h[maxn]; void fstread(int &x){
char ch = getchar();x = ;
while(ch > '' || ch < '') ch = getchar();
while(ch >= '' && ch <= '') x = x*+ch-'',ch=getchar();
} int chk(int x,int k){
return rk[sa[x]]==rk[sa[x-]]&&rk[sa[x]+(<<k)]==rk[sa[x-]+(<<k)];
} void GetSA(){
for(RI int i=;i<n;i++) X[str[i]]++;
for(RI int i=;i<=N;i++) X[i] += X[i-];
for(RI int i=n-;i>=;i--) sa[X[str[i]]--] = i;
for(RI int i = , num = ;i <= n;i++)
rk[sa[i]] = (str[sa[i]] == str[sa[i-]]?num:++num);
rk[sa[]] = ;
for(int k=;(<<k-)<=n;k++){
for(RI int i=;i<=N;i++) X[i] = ;
for(RI int i=n-(<<k-);i<n;i++) Y[i-n+(<<k-)+]=i;
for(RI int i=,j=(<<k-)+;i<=n;i++)
if(sa[i]>=(<<k-))Y[j++]=sa[i]-(<<k-);
for(RI int i=;i<n;i++) X[rk[i]]++;
for(RI int i=;i<=N;i++) X[i]+=X[i-];
for(RI int i=n;i>=;i--) sa[X[rk[Y[i]]]--] = Y[i];
int num = ; Y[sa[]] = ;
for(RI int i=;i<=n;i++) Y[sa[i]] = (chk(i,k-)?num:++num);
for(RI int i=;i<n;i++) rk[i] = Y[i];
if(num == n) break;
}
} void buildRMQ(){
for(int i=;i<=n;i++) RMQ[i][] = ht[i];
for(int i=;(<<i)<=n;i++) pw[(<<i)] = i;
for(int i=;i<=n;i++) if(!pw[i]) pw[i] = pw[i-];
for(int k=;(<<k)<=n;k++){
for(RI int i=;i<=n;i++){
if(i+(<<k-)>n) RMQ[i][k] = RMQ[i][k-];
else RMQ[i][k] = min(RMQ[i][k-],RMQ[i+(<<k-)][k-]);
}
}
} void GetHeight(){
for(RI int i=;i<n;i++){
if(i) h[i] = max(,h[i-]-);
if(rk[i] == ) {h[i] = ;continue;}
while(str[i+h[i]] == str[sa[rk[i]-]+h[i]]) h[i]++;
}
for(RI int i=;i<n;i++) ht[rk[i]] = h[i];
} int LCP(int l,int r){
l = rk[l],r = rk[r]; if(l > r) swap(l,r);l++;
int k = pw[r-l+];
return min(RMQ[l][k],RMQ[r-(<<k)+][k]);
} void update(int now,int tl,int tr,int pos,int len){
if(tl == tr){T[now] = max(T[now],len); return;}
int mid = (tl+tr)/;
if(pos <= mid) update(now<<,tl,mid,pos,len);
else update(now<<|,mid+,tr,pos,len);
T[now] = max(T[now<<],T[now<<|]);
} int Query(int now,int tl,int tr,int l,int r,int mx){
if(tl >= l && tr <= r){
if(T[now] <= mx) return -;
else{
while(tl < tr){
int mid = (tl+tr)/;
if(T[now<<|] > mx) tl = mid+,now = now*+;
else tr = mid,now<<=;
}
return tl;
}
}
if(tl > r || tr < l) return -;
int mid = (tl+tr)/;
if(mid >= r) return Query(now<<,tl,mid,l,r,mx);
if(mid < l) return Query(now<<|,mid+,tr,l,r,mx);
int z = Query(now<<|,mid+,tr,l,r,mx);
if(z!=-) return z;
else return Query(now<<,tl,mid,l,r,mx);
} vector<int> mlgb[maxn]; namespace BruteForce{
int minn[maxn<<]; pair<int,int> QueryRange(int now,int tl,int tr,int l,int r,int up,int d){
if(tl >= l && tr <= r && d == ){
if(minn[now] < up){
while(tl != tr){
int mid = (tl+tr)/;
if(minn[now<<|] < up) tl = mid+,now=now*+;
else tr = mid,now<<=;
}
return make_pair(minn[now],tl);
}else return make_pair(,);
}
if(tl >= l && tr <= r && d == ){
if(minn[now] < up){
while(tl != tr){
int mid = (tl+tr)/;
if(minn[now<<] < up) tr = mid,now<<=;
else tl = mid+,now=now*+;
}
return make_pair(minn[now],tl);
}else return make_pair(,);
}
if(tl > r || tr < l) return make_pair(,);
int mid = (tl+tr)/;
if(mid>=r) return QueryRange(now<<,tl,mid,l,r,up,d);
if(mid<l) return QueryRange(now<<|,mid+,tr,l,r,up,d);
if(d){
pair<int,int> z = QueryRange(now<<|,mid+,tr,l,r,up,d);
if(z.first) return z;
else return QueryRange(now<<,tl,mid,l,r,up,d);
}else{
pair<int,int> z = QueryRange(now<<,tl,mid,l,r,up,d);
if(z.first) return z;
else return QueryRange(now<<|,mid+,tr,l,r,up,d);
}
}
void add(int now,int tl,int tr,int pos,int dt){
if(tl == tr) {minn[now] = dt;return;}
int mid = (tl+tr)/;
if(pos <= mid) add(now<<,tl,mid,pos,dt);
else add(now<<|,mid+,tr,pos,dt);
minn[now] = min(minn[now<<],minn[now<<|]);
} void holyshit(){
memset(minn,0x3f,sizeof(minn));
for(int i=n-;i>=;i--){
int z = rk[i],p=;
add(,,n,z,i);
while(true){
pair<int,int> um = QueryRange(,,n,z+,n,p,);
if(!um.first) break;
mlgb[um.first].push_back(i);
z = um.second; p = sa[z];
}
z = rk[i],p = ;
while(true){
pair<int,int> um = QueryRange(,,n,,z-,p,);
if(!um.first) break;
mlgb[um.first].push_back(i);
z = um.second; p = sa[z];
}
} }
} void work(){
GetSA();
GetHeight();
buildRMQ(); BruteForce::holyshit();
int num = ;
for(int i=;i<n;i++){
for(int j=;j<mlgb[i].size();j++){
int z = LCP(mlgb[i][j],i);
if(a[mlgb[i][j]] >= z) continue;
a[mlgb[i][j]] = z;
update(,,n-,mlgb[i][j],z); }
while(qy[num].r == i){
int z = ,pq = qy[num].r-;
while(pq >= qy[num].l){
int hp = Query(,,n-,,pq,z);
if(hp < qy[num].l) hp = qy[num].l-;
ans[qy[num].nb] += (pq-hp)*z;
if(hp < ) break;
z = a[hp],pq = hp;
}
num++;
}
}
for(int i=;i<=q;i++) printf("%d\n",ans[i]);
} int cmp(node alpha,node beta){return alpha.r < beta.r;}
int main(){
//freopen("1.in","r",stdin);
fstread(n);fstread(q);
for(int i=;i<=n;i++){
str[i-] = getchar();
while(str[i-]!= '' && str[i-] != '') str[i-] = getchar();
}
for(int i=;i<=q;i++) fstread(qy[i].l),fstread(qy[i].r),qy[i].nb=i;
for(int i=;i<=q;i++) qy[i].l--,qy[i].r--;
sort(qy+,qy+q+,cmp);
work();
return ;
}