自动搬运

查看原文

来自洛谷，原作者为

	iostream Think three times, code twice and take the first place.

搬运于2025-08-24 22:17:57，当前版本为作者最后更新于2020-05-21 23:27:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目描述

给定一个长度为 $n$ 的字符串 $P$，有 $m$ 次询问，每次给定两个参数 $l$ , $r$，询问子串 $P[l,r]$ 所构成的后缀树的结点数。

$n\le 10^5,m\le 3\times 10^5$

题解

tag：分类计数；后缀树/后缀自动机；线段树/树状数组；哈希。

做法来自2018集训队论文集。

由于构建后缀树需要倒转原串之后建立 SAM 得到，为方便处理，故我们先倒转原串以及对应询问区间。

下文例子的字符串都是倒转之后的。

记 $node_{[l,r]}$ 表示找区间 $[l,r]$ 对应子串在后缀树上的节点。

考虑传统后缀树节点数的计数方法，对于一个区间 $[l,r]$ 建后缀自动机的过程，产生出了 np 和 nq 两种类型的节点。

np 节点对应的是 $i\in [l,r]$ 的前缀 $[l,i]$ 对应的串，暂时称作前缀节点；

nq 节点对应的是后缀树上必要的分叉，暂时称为分裂节点；

example："pabcqabc"

对于 "abc" 这个串，子树分成 "pabc" 和 "qabc" 两个独立的节点，故 "abc" 本身新建了一个分裂型节点。

考虑容斥，计算前缀节点个数 + 分裂节点个数 - 前缀&分裂节点的个数。

前缀节点个数

可以直接得到，即 $r-l+1$。

分裂节点个数

放到后缀树上考虑，依然以上串 "pabcqabc" 为例：

"abc" 这个串在树上产生分叉（你考虑后缀树中实际相当于插入了 "cbap" 跟 "cbaqcbap" 俩串）的必要条件是其在当前区间中出现 $\ge 2$ 次，且存在两个出现位置，其往前一个位置的字符不同。

预处理整个串的后缀自动机以及树，离线询问。

考虑按右端点扫描线，扫到 $r$ 的时候，将 $[1,r]$ 对应的字符串 $node_{[l,r]}$ 标记上 $r$ 这个位置。

现在等价于求有多少个节点 $u$，当前存在两个不同子树中的 $pos_a$、$pos_b$ 使得 $pos_a -len_u\ge l$ 且 $pos_b-len_u\ge l$，那么 $u$ 对应的节点将在 $[l,r]$ 中作为分裂节点出现。

这个是个传统树上数据结构题，一种好写的方法是 lct 维护后缀树，access 更新过程中从 $root$ 到 $node_{[1,r]}$ 的路径上染上 $r$ 这种颜色，再维护每个节点来自不同子树最后两次染上的颜色分别是 $lst_u$ 和 $now_u$，然后再用树状数组维护树上所有节点的 $lst_u-len_u$，这样查询树状数组上 $\ge l$ 的部分的和就是分裂节点的个数。

这一段时间复杂度是 $O(n\log^2 n+m\log n)$，来自于 lct 和树状数组。

接下来还需要计算前缀&分裂节点的个数。

考虑一种可行的暴力，枚举所有 $i\in [l,r]$ 找到 $node_{[l,i]}$ 的位置 $p$(※)，然后再判断该位置是否有两个或以上子树，然后再判断是否 $lst_p\gt mid$，仅当全部为“是”就对答案带来 $-1$ 的贡献。

(※)笔者注：这个位置不一定恰好是树上的点，可能在边上，在边上显然不满足有两个或以上子树。这个位置就是对应的前缀节点将产生的位置，也就意味着，对 $[l,r]$ 这个区间建后缀树，所有的分裂节点一定是整个长串的后缀树上节点的子集，而 $r-l+1$ 个前缀节点不一定全是。

接下来将该暴力优化至 $O(m\log n)$ 的复杂度：

引理：所有可行的 $i\in [l,r]$ 是一段前缀。

证明：显然一个串 $[l,i]$ 能找到两个出现位置，其往前一个位置的字符不同，则 $[l,i-1]$ 也可以。

example："abcdabceabc"

其中 "abc" 作为分裂&前缀节点出现，可以直接说明前三个前缀节点均算重了。

有了引理，就可以上一个二分，每次 check $[l,mid]$ 这个串是否形成分裂节点即可。

在后缀自动机上找 $node_{[l,mid]}$ ，传统方法是利用倍增预处理，单次以 $O(\log n)$ 的复杂度查询；

判定分裂节点可以直接用上一部分算出的 $lst_u$ 来直接判断；

该算法复杂度为 $O(m\log^2 n)$。

但是这玩意还可以进一步优化，注意到 $u$ 是分裂节点的必要条件是 $u$ 有两个或更多子树。

后缀树上有两个或更多子树的串只有 $O(n)$ 个，可以考虑用字符串哈希预处理其对应的节点。

二分的时候如果在哈希表中难以找到 $[l,mid]$ 这个串，就说明该串在树边上而非节点上，一定不会成为分裂节点。

那么只需要二分找到最大的 $mid$ ，容斥掉的点数即为 $mid-l+1$。

该算法复杂度为 $O(m\log n)$。

需要代码可以去这里查看。