题意简述
给定字符串 $S$,设 $suf(i)$ 表示从 $i$ 开始的后缀。支持 $q$ 个询问,每次给定 $[l,r]$,求这段区间中有多少对 $i,j$ 使得 $suf(i)$ 和 $suf(j)$ 的最长公共前缀长度 $\ge k$。$k$ 是一个定值,每次都一样。
(备注:$(i,j)$ 和 $(j,i)$ 是同样的一对,只算一次)
$k\le |S|\le 3\times 10^6,m\le 10^5$,并且满足 $n^2m\le 10^{15}$。
思路
$n^2m\le 10^{15}$?这看起来很奇怪。
冷静分析一下,这提示着我们,$O(n\sqrt{m})$ 的算法是可以通过的。仔细想一下 ,带根号的静态区间询问的算法…
莫队 !
然后,$suf(i),suf(j)$ 最长公共前缀长度 $\ge k$,等价于:$i$ 往后 $k$ 个的子串,和 $j$ 往后 $k$ 个的子串相同。
然后我们要快速比较两端子串是否相同…
哈希 !
于是问题变为:
- 处理第 $i$ 位往后 $k$ 个位置的哈希值,设为 $h[i]$
- 每次询问,就相当于询问 $h[l,r]$ 中有多少不重复的数,显然可以莫队维护。
代码
1 |
|