题解 P6152 【[集训队作业2018] 后缀树节点数】

iostream · 2020-05-21 23:27:55 · 题解

题目描述

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

题解

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)。

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