UOJ Logo Itst的博客

博客

#700 另一个做法

2022-01-09 20:20:18 By Itst

因为马哥哥已经跟我说了标算是 polylog 所以这个肯定是另法了……

对字符串按 $\sqrt{n}$ 分块,对于一组询问 $(l,r)$,如果其长度小于 $2\sqrt{n}$ 暴力,否则找到这一段覆盖到的第一个块端点 $x$,有 $x-l \leq \sqrt{n}$。先跑出 $[x,r]$ 的答案,这可以离线后对每个块端点跑一次 kmp,然后分开计算长度小于等于 $x-l$ 和大于 $x-l$ 的前缀 border 的贡献。

长度小于等于 $x-l$ 的部分暴力枚举 border 长度 $l_0$,则需要计算的是 $[l+l_0,r]$ 上所有 $s_{l \sim l+l_0-1}$ 的 endpos 的贡献和。放在 SAM 上这东西就是一个二维偏序,询问定位可以在 SAM 的 DAG 上跑所以是 $O(1)$,将所有询问离线下来扫描线,用 $O(\sqrt{n})$ 修改 $O(1)$ 询问的数据结构维护即可做到 $O(m\sqrt{n})$。因为空间限制比较紧不能直接存 $O(m\sqrt{n})$ 个询问,所以需要一点小技巧将空间优化到线性,留给读者自行思考

某个蠢人场上二维偏序写了 $O(n \sqrt{n} \log n)$ 然后想了一万年怎么优化我不说是谁

长度大于 $x-l$ 的 border 则可以利用 $(x,r)$ 的信息,这是因为如果 $(l,m)$ 有一个 border 长度为 $l_1 > x-l$,则 $(x,m)$ 一定对应有一个长度为 $l_1-(x-l)$ 的 border。所以 $(l,r)$ 的长度大于 $x-l$ 的 border 的贡献和一定是在 $(x,r)$ 答案的基础上减掉一些 $(x,r)$ 有但 $(l,r)$ 就没有的 border 的贡献。

具体地,考虑一个点 $p \in [x+1,r]$,则其在 $s_{x \sim r}$ 中的贡献是 $w_p+w_{p+1}+w_{p+2}+\cdots+w_{\min(r,p+\mathrm{lcp}(x,p) - 1)}$,而这个贡献能够出现在 $(l,r)$ 中的充要条件是 $\mathrm{lcs}(x-1,p-1) \geq x-l$。所以将 $(x,r)$ 调到 $(l,r)$ 的贡献变化是 $-\sum_{i=x+1}^r [\mathrm{lcs}(x-1,i-1) < x-l] sumw_{\min(r,i+\mathrm{lcp}(i,x)-1)} - sumw_{i-1}$。

对于一个确定的 $x$,lcp 与 lcs 的其中一个参数是确定的,所以算 lcp 可以每次算一遍扩展 kmp,算 lcs 可以在 SAM 的 parent 树上打差分标记然后 dfs 做个路径和,都是 $O(n \sqrt{n})$ 的。$-\sum_{i=x+1}^r [\mathrm{lcs}(x-1,i-1) < x-l] sumw_{\min(r,i+\mathrm{lcp}(i,x)-1)} - sumw_{i-1}$ 这东西的计算又是一个二维偏序。按照 $r$ 扫描线,以 $\mathrm{lcs}(x-1,i-1)$ 作为下标存贡献就行,$\min$ 里面的元素产生变化时进行一下调整。乍一看还是要带 $\log$,但是 $x-l \leq \sqrt{n}$ 所以 $\mathrm{lcs}(x-1,i-1)$ 可以跟 $\sqrt{n}$ 取 $\min$,所以不用数据结构暴力维护长度为 $\sqrt{n}$ 的数组然后每次暴力算前缀和就行。

评论

EntropyIncreaser
Itst 生日 AK 候选队互测.

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。