「Summary」2023-04-08 做题记录

听不懂了。

CF700E

首先对字符串建 SAM ,用可持久化线段树维护每个节点的 $\mathrm{right}$ 集合,在 $\mathrm{parent}$ 树上 dp ,$dp_i$ 表示到 $i$ 节点时 $k$ 的最大值,如果某个父节点的子串在子结点中出现了不止一次,则子结点的 $dp$ 加一。
具体来说,判断父节点 $u$ 的子串在子结点 $v$ 中出现了不止一次的方法是查询 $v$ 的 $\mathrm{right}$ 集合中是否存在一个 $pos$ 在 $[pos - len_u + len_v, pos - 1]$ 处出现过即可。