当用 SA 来建后缀树

因为学不会什么串串技术，所以我只会 SA，至于 SAM 啥的我一窍不通，而后缀树也只知道定义！所以别和我说 Ukkonen 算法，因为我不会。

以下假设原串 \(\text{S}\) 长度为 \(n\)，我们在后缀数组 \(\text{SA}\) 开头插入一个空串，用 \(\text{H}\) 数组（好像通常叫做 \(\text{height}\) 数组？）表示 \(\text{SA}\) 上相邻两个串的 \(\operatorname{lcp}\) 长度；即 \(\text{SA}_0=\varnothing\)，\(\text{H}_{k}=\operatorname{len}(\operatorname{lcp}(\text{SA}_{k-1},\text{SA}_{k}))\)。

建立 \(\text{SA}\) 的复杂度一般是 \(O(n\log n)\) 或者 \(\Theta(n)\) 的，建立 \(\text{H}\) 的复杂度一般是 \(\Theta(n)\) 的。我们以下就不妨认为该部分预处理的复杂度为 \(O(n\log n)\) 的。通常来说，只要 SA 部分的常数实现得足够好，该部分就不会成为瓶颈。

后缀树是由原串 \(\text{S}\) 的每个后缀串所组成的 Trie。容易发现其节点个数是 \(O(n^2)\) 的。

后缀树的特殊之处在于，其仅仅只用记录 \(\Theta(n)\) 个后缀的信息。

因此，我们其实并不用建出后缀树作为 Trie 的本身，而只用建出其对应的压缩 Trie 即可。

怎么办？

注意到压缩 Trie 其实就是由各个后缀所对应的节点构成的一颗虚树，我们只用建出这颗虚树即可！

容易发现，\(\text{SA}\) 本身的顺序就是这些后缀树上关键点按 dfn 序排列所得结果，而 \(\text{H}\) 数组标识着 \(\text{SA}\) 序上相邻两个关键点的 \(\text{lca}\) 深度。于是我们直接按 \(\text{SA}\) 序插入节点即可建出虚树。

这样我们就建出了一颗压缩后的后缀树。

如果想要每个关键节点都是叶子节点从而来简化讨论，我们通常可以在原串 \(\text{S}\) 的末尾添加一个特殊字符 \(\tt\$\)，这样每个后缀都是互不包含的，并且 \(\operatorname{lcp}\) 大小不会发生改变。

例题 区间本质不同子串个数

我们先建出一颗后缀树。

对左端点从右往左作扫描线，每次加入一个后缀，也就是后缀树上一条到根的路径。

在后缀树上每个节点处记录上其最后一次被覆盖的时间 \(t_p\)，以及其深度 \(d_p\)。

容易发现，在原本的 Trie 上，一个节点对某个 \(r\) 有贡献，当且仅当 \(t_p+d_p\le r\)。

在压缩 Trie 上，每条边标志的节点的 \(d_p\) 是一段连续的区间，而 \(t_p\) 与该边下部连接的节点相同。

于是我们就要支持若干次更改到根为止的 \(t\)。

考虑暴力维护各个颜色段对应的链顶，暴力切换，使用树剖 / GBT 来维护颜色。

然后使用 LCT 的均摊分析，可以证明颜色切换总次数是 \(O(n\log n)\) 级别的。

维护每个 \(t_p+d_p\) 有多少个，单次修改就是区间 \(\pm1\)，单次询问就是前缀求和，拿个 BIT 做一下即可；如果要求强制在线，可以使用主席树维护。

总复杂度 \(O(n\log^2n+q\log n)\)。

代码咕了。

例题 「NOI2018」你的名字

我们离线下来，在修改串和询问串中间塞特殊字符，末尾塞一个特殊字符，建出一颗后缀树。

然后类似于刚刚的做法，对左端点扫描线，每次加入一个后缀。

查询的部分需要做一个容斥（计算原本的本质不同子串数目减去在 \(T_{l,r}\) 中出现的部分），并且还需要一个树上二分。

在 \(T_{l,r}\) 中出现的部分的贡献较为繁杂，因为一个二分出来的节点可能会在压缩 Trie 的一条边上出现，所以需要先去重，然后再计算该部分贡献，再扣除相邻两项的 \(\operatorname{lcp}\) 长度（显然 \(\operatorname{lcp}\) 必然只会在顶点处出现）。

我使用了全局平衡二叉树实现，总复杂度 \(O((n+q)\log n)\)。需要非常注意建后缀数组部分的常数。

如果强制在线也能做，但是会难写很多。（每次得单独二分，不能直接预处理建出 \(\text{SA}\) 了）

代码实现。