由于译者个人原因, 本文与原文有极大出入, 真是不好意思

origin

IntroDuction

问题是这样的: 多次查询一个字符串 $S$ 的某个子串的不同子串个数.

{…}emm, 直接进入正题吧!

Solution

让我们回忆某个求区间不同元素个数的离线 Sol. 你可以将询问按右端点排序, 在 $r$ 处我们保持 $(b[i] = 1)$ iff $i$ 是最后一个 $S[i]$ ($[1, r]$ 里), 否则 $(b[i] = 0)$. 那么你就可以查询某个 $[l, r]$ 的答案啦, 考虑 $b$ 数组在 $r$ 时的状态, 区间 $[l, r]$ 求和.

(当然可以使用主席树进行在线询问)

现在我们扔掉我们的字符串然后一个个地添加字符, 维护后缀自动机. 我们维护 $b[i]$ 等于最后出现的 $S[i, j]$ 个数总和 (就是对于相同的子串我们只计左端点最右的, 在 $b[i]$ 上). 然后询问就简单了.

怎么维护 $b[i]$ ? 首先我们对于全串建出一颗后缀树. 对于所有的新后缀…当然…所以我们要 $b[1...n] ++$. 现在我们应当找到位置: 不再是最右的子串. 然后将它们位置的贡献减掉.

你可能会注意到, 在后缀树你将会更新从当前节点 (让我们称她为 $p$)到根 ($rt$)的所有节点. 为了叙述的方便, 我们使得后缀树某个节点的颜色表示他们 $endpos$ 的当前最后. 我们将更新从 $p$ 至 $rt$ 的所有节点, 当然不是狂扫, 对于一段连续的颜色我们也是连续地更新 (一段一段地往上跳), 这个具体实现想必维护一个 $up$ 数组就好了.

这个具体实现想必维护一个 $up$ 数组就好了

其实当我半年 (或者一年?) 后再次看到这里的时候是一脸懵逼的, 于是写得具体点好了, 我们更新当前节点的时候, 将其染色为上一次染的颜色 $+1$, 这样每个节点最后被更新的颜色就是其子树内颜色的最大值, 这是可以 $O(\log n)$ 查询的, 然后对于每个颜色 (一条链) 维护最上点, 就好了.

然后总的时间复杂度是 $O(n \log n\log n)$ 的.

呵, 你问我为什么. 首先线段树一个 $\log$, 然后往上跳那个东西均摊是 $O(n \log n)$ 的, 因为树链剖分后所有轻边 $sz$ 总和为 $O(n \log n)$. (这大概会成为一个trick吧)