题目
题解
首先一个暴力做法就是把这题看成这题，然后暴力枚举就行了
发现有个随机条件……
你揣兜估计一下既然随机还只有$01$，$lcp$长度应该不大长，写个程序跑跑发现好像不大于$40$
那么就用$Trie$来维护$lcp$，枚举每一位和往后的$40$位，在$Trie$加入这$40$个串，每个点位置维护这个子串出现的最右位置，然后维护当前点代表的后缀对于每个$lcp$能找到的最右端点（代表的后缀），然后统计一下即可
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<set>
# include<algorithm>
using namespace std;
const int MAX=1e5+5;
struct p{
int l,r,id;
bool operator< (const p &a)
const{
return r<a.r;
}
}qu[MAX];
int n,Q,tot;
int f[41],ans[MAX];
char a[MAX];
struct Trie{
int id[MAX*40];
int son[MAX*40][2];
void ins(int l)
{
for(int i=l,x=0;i<=l+40&&i<=n;++i)
{
if(!son[x][a[i]-'0']) son[x][a[i]-'0']=++tot;
x=son[x][a[i]-'0'],f[i-l+1]=max(f[i-l+1],id[x]),id[x]=l;
}
}
}_T;
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
int main()
{
n=read(),Q=read(),scanf("%s",a+1);
for(int i=1;i<=Q;++i)
qu[i].l=read(),qu[i].r=read(),qu[i].id=i;
sort(qu+1,qu+1+Q);
for(int i=1,L=1;i<=n;++i)
{
_T.ins(i);
while(i==qu[L].r&&L<=Q)
{
for(int j=1;j<=40;++j)
if(f[j]>=qu[L].l) ans[qu[L].id]+=j*(f[j]-max(f[j+1],qu[L].l-1));
else break;
++L;
}
}
for(int i=1;i<=Q;++i)
printf("%d\n",ans[i]);
return 0;
}
