FlyInTheSky's Blog

Loj 2312
题意：给出一个 $n​$ 位随机 $01​$ 串，定义 $\text{data}(l,r)=\max(\text{LCP}(\text{Suf}_i,\text{Suf}_j)|i≠j,l≤i,j≤r)​$ 。
给出 $m​$ 个询问 $[l,r]​$ ，求

$$\sum\limits_{i=l}^{r-1}\text{data}(i,r)$$

题目说随机生成，那么估计LCP相同的概率为$({1\over 2})^{len} \cdot C^{2}_{r-l+1}$，在取$40$时，这个几率已经很小，我们直接对于每个后缀存前$40$个字符即可。考虑依次加入每个位置的后缀

我们发现对于一个区间$[l,r]$的答案，一定比$[l+1,r], [l+2,r], \dots , [r-1,r]$答案更大，因为他们是包含关系
那么我们可以运用这个单调性，还能发现答案是一块一块的，我们联想到数论分块的思想。

设$pos(i,j)$为$[1,i]$中后缀$\exists \text{LCP}=j$的最大位置。
那么求答案我们分成一块一块地求，具体看代码注释。

知识点：
1、单调性运用 (类似品酒大会从后往前求答案)
2、离线思想 (按某元素排序)