题目概述

给出一个 $n$ 位随机 $01$ 串，定义 $data(L,R)=max\{LCP(Suf_i,Suf_j)|i\not=j,L\le i,j\le R\}$ 。

给出 $m$ 个询问 $[L,R]$ ，求 $\sum_{i=L}^{R-1}data(i,R)$ 。

解题报告

随机 $01$ 串……粗略估计相同的概率为 $({1\over 2})^{len}{R-L+1\choose 2}$ ，那么 $len=50$ 的时候概率就很低了，所以假装 $LCP$ 最大只有 $50$ ，然后我就不会了。

可以发现从 $R​$ 往前，$data(i,R)​$ 显然是递增的，所以我们可以记录 $pos_{R,j}​$ 表示 $R​$ 往前的第 $j​$ 个分段处，然后每次询问只需要 $O(50)​$ 回答。

怎么构造 $pos$ ？两种方法：1.二分+哈希验证。2.从小到大求 $pos_R$ ，每次加入 $R$ 这个位置，用Trie更新长度为 $j$ 的配对的最晚出现时间 $MAX_j$ ，$pos_{R,j}=\begin{cases}MAX_j&\forall MAX_k<MAX_j,k>j\\0&\exists MAX_k>MAX_j,k>j\end{cases}$ 。

示例程序

#include<cstdio>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=100000,maxl=50,maxt=maxn*maxl;

int n,te,pos[maxn+5][maxl+5];char s[maxn+5];
int si,son[maxt+5][2],lst[maxt+5],now[maxl+5];

inline void Insert(int L,int R){
    for (int i=L,j=1,p=0;i<=R;i++,j++){
        if (!son[p][s[i]-48]) son[p][s[i]-48]=++si;
        p=son[p][s[i]-48];now[j]=max(now[j],lst[p]);lst[p]=L;
    }
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d%d%s",&n,&te,s+1);
    for (int i=1;i<=n;i++){
        Insert(i,min(i+50,n));for (int j=1;j<=50;j++) pos[i][j]=now[j];pos[i][0]=i-1;
        for (int j=50,MAX=0;j;j--) if (MAX>pos[i][j]) pos[i][j]=0; else MAX=pos[i][j];
    }
    for (int i=1;i<=te;i++){
        int L,R,lst=0,ans=0;scanf("%d%d",&L,&R);
        for (int j=1;j<=50;j++)
            if (pos[R][j]) {if (pos[R][j]<L) break;ans+=(pos[R][lst]-pos[R][j])*lst;lst=j;}
        printf("%d\n",ans+(pos[R][lst]-L+1)*lst);
    }
    return 0;
}