自动搬运

查看原文

来自洛谷，原作者为

	世凪 明日は明日の風が吹く

搬运于2025-08-24 22:40:16，当前版本为作者最后更新于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)$。