「Loj 2312」「HAOI2017」供给侧改革 (Trie + 类似数论分块)

Loj 2312
题意:给出一个 nn​ 位随机 0101​ 串,定义 data(l,r)=max(LCP(Sufi,Sufj)ij,li,jr)\text{data}(l,r)=\max(\text{LCP}(\text{Suf}_i,\text{Suf}_j)|i≠j,l≤i,j≤r)​
给出 mm​ 个询问 [l,r][l,r]​ ,求

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

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

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

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

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

Read more