P8571 [JRKSJ R6] Dedicatus545

世凪 · 2022-10-25 19:27:09 · 题解

不知道为什么要猫树分治。

首先建出 AC 自动机。

考虑根号分治，记 N = \sum |s|, B = \sqrt N。

如果 |s_k| \geq B，不同的 k 不会超过 B 个，对于每个 k，把该串在 AC 自动机上的每个点权值加 1，然后求出每个点的子树权值之和。这样就可以知道每个点在 s_k 的出现次数，用线段树维护区间最大值，这部分复杂度是 O((n+N)\sqrt N + m \log n)。

如果 |s_k| < B，考虑对 s_k 建立虚树，如果某个虚树上的点 x 到根的路径上存在某个 [l, r] 的终止节点，说明答案至少是 siz_x（siz_x 表示虚树中 x 的子树大小）。

对 r 做扫描线，维护每个点到根的最大标号，如果这个标号 \geq l 说明合法，因此需要一个区间取 \max，单点查询的数据结构。可以用分块做到 O(\sqrt N) - O(1)。

这部分复杂度是 O(N\log N + (n+m)\sqrt N)。