题意简述
给定一个随机生成的长度为 (n) 的由0和1构成的字符串 (S)。
(data(l,r)) 表示：在字符串 (S) 中，起始位置在 ([l,r]) 之间的这些后缀之中，具有最长公共前缀的两个后缀的最长公共前缀的长度。
(m) 次询问，每次给定 (l,r) ，求 (sumlimits_{lleq i < r} data(i,r)) ，不强制在线。
(n,m leq 10^5)
想法
注意到“随机生成”，那么两个长度为 (x) 的字符串完全相同的概率为 (frac{1}{2^x})。
当 (x=40) 时这个概率就很小了，所以可认为最长公共前缀的长度 (leq 40)。
将询问离线，按 (r) 从小到大排序。
维护一棵深度40的 (trie) 树。
从左到右扫，(trie) 树中起始位置在 (i) 的后缀。
显然 (data(1,i)geq data(2,i) geq ... geq data(i-1,i))
维护数组 (h[])，其中 (h[x]=y) 表示 (y) 是满足 (data(y,i)geq x) 的最大值。
换句话说，(data(1,i)geq data(2,i) geq ... geq data(y,i) geq x > data(y+1,i))
那么对于所有 (r=i) 的询问，将 (h[]) 扫一遍，与 (l) 比比大小再运算便可得到 (ans) ，因为 (h[]) 下标最大40，所以时间上不成问题。
最后一个问题，每加入一个新后缀时，如何更新 (h[]) 呢？
(trie) 树中每个点 (x) 都记录一下之前最后访问该点的那个后缀的起始位置 (lst[x])，新加入的后缀走到深度为 (d) 的点 (x) 时，(lst[x]) 开头的后缀与此新后缀的公共前缀至少为 (d) ，也就是 (data(lst[x],i)geq d) ，所以更新 (h[d]=max(h[d],lst[x]))
总复杂度 (O(40n))
总结
抓住“随机”找特点；抓住小的数据点。
（感觉这个题有点神，虽然代码很短但不太好想……）
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x;
}
const int N = 100005;
int n,m;
char s[N];
struct data{
int l,r,id;
bool operator < (const data &b) const{ return r<b.r; }
}d[N];
int ans[N],h[45];
int cnt,root,ch[N*40][2],lst[N*40];
void ins(int id){
int x=root,y;
for(int i=0;i<40 && i+id<=n;i++){
y=s[i+id]-'0';
if(!ch[x][y]) ch[x][y]=++cnt;
x=ch[x][y];
h[i+1]=max(h[i+1],lst[x]);
lst[x]=id;
}
}
int main()
{
n=read(); m=read();
scanf("%s",s+1);
for(int i=1;i<=m;i++) d[i].l=read(),d[i].r=read(),d[i].id=i;
sort(d+1,d+1+m);
root=++cnt;
int t=1;
for(int i=1;i<=n;i++){
if(t>m) break;
ins(i);
for(int j=39;j>0;j--) h[j]=max(h[j],h[j+1]);
while(t<=m && d[t].r==i){
for(int j=1;j<=40;j++){
if(h[j]<d[t].l) break;
ans[d[t].id]+=h[j]-d[t].l+1;
}
t++;
}
}
for(int i=1;i<=m;i++) printf("%d
",ans[i]);
return 0;
}