题意

给定长度为 的字符串 ，给定 组询问 ，求 ，数据随机。

思路

发现数据随机，那么存在 长度为 的概率为 ，故大概 的时候就不存在了（当然要是考场做我会开 ）。

于是每个后缀只有前面 个是有用的，先塞进 Trie 里。

然后考虑 ，如果 ，那么 ，我们固定右端点，那么就有两种情况：

1. ；
2. 。

我们发现第二种情况满足 变小时单调不降，也就是一个 的贡献会一直向前持续。

故我们枚举这个长度 ，这样就存在一个最后一个满足 的 ，记其为 ，那么贡献是好算的。

而且这个 计算与 无关（ 只在计算贡献的时候作为参数），故上述两种情况变为： 最后一个满足条件的前缀可在 Trie 上求得。

时间复杂度为 ，其中 为 的期望最大长度。

CODE

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010,M=40,FSIZE=1<<26;
int n,q,last[N][M+5];
struct Trie{
    struct node{
        int s[2],last;
    }a[N*(M+5)];
    int size;
    void add(char *s,int x){
        int i=0,rt=0;
        for(;++i<M&&*s>32;++s){
            int &n=a[rt].s[*s^48];
            if(!n) n=++size;
            last[x][i]=exchange(a[rt=n].last,x);
        }
    }
}t;
char BuF[FSIZE],*InF=BuF,*s;
template<typename T>void read(T &x){
    for(;48>*InF||*InF>57;++InF);
    for(x=0;47<*InF&&*InF<58;x=x*10+(*InF++^48));
}
int main(){
    fread(BuF,1,FSIZE,stdin);
    read(n);read(q);
    for(;*InF<33;++InF);
    s=InF-1;
    for(int i=1;i<=n;++i){
        t.add(s+i,i);
        for(int j=1;j<=M;++j) last[i][j]=max(last[i][j],last[i-1][j]);
    }
    for(;*InF>32;++InF);
    for(int l,r;q--;){
        int sum=0;
        read(l);read(r);
        for(int i=M;i;--i)
            if(last[r][i]>=l){
                sum+=(last[r][i]-l+1)*i;
                l=last[r][i]+1;
            }
        printf("%d\n",sum);
    }
    return(0);
}