自动搬运

查看原文

来自洛谷，原作者为

	fjy666 请将我幻葬

搬运于2025-08-24 22:55:26，当前版本为作者最后更新于2024-02-27 13:20:59，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

考虑根号分治，设阈值为 $B$。

Case 1. $|s|\le B$

对于一个询问 $(l,r,k)$，记录 $f_i$ 为 $\operatorname{prefix}(s_k,i)$ 在 $a_l\sim a_r$ 中的出现次数，$g_i$ 为 $\operatorname{suffix}(s_k,i)$ 在 $a_l\sim a_r$ 的出现次数，则

差分一下，变成前缀对串的贡献。我们可以建立 AC 自动机，单点加子树求和。

可以用 $\mathcal{O}(\sqrt{m})-\mathcal{O}(1)$ 的分块根号平衡复杂度。

总时间复杂度为 $\mathcal{O}(qB+m\sqrt{m})$。

Case 2. $|s|>B$

这个长度不允许我们对于单组询问解决时间复杂度带 $|s|$。

Solution 1

设 $s_k=a+b$，当 $|a|\le B$ 或 $|b|\le B$ 的时候可以像 Case 1 一样做。

当 $|a|>B$ 且 $|b|>B$ 时，它们所对应的字符串只有 $\mathcal{O}(\frac{m}{B})$ 种。

那么本质不同询问左端点 $l$ 也只有 $\mathcal{O}(\frac{m}{B})$。

直接暴力计算每种本质不同询问的答案，复杂度是 $\mathcal{O}(\frac{m^3}{B^2})$。

取 $B=n^{2/3}$ 得到最优复杂度 $\mathcal{O}(n^{5/3})$。

Solution 2

长度 $>B$ 的字符串共 $\mathcal{O}(\frac{m}{B})$ 个。对于一个 $k$，我们预处理出 $cnt_{i,j}$ 表示 $\operatorname{prefix}(s_k,j)$ 在 $s_i$ 中的出现次数。（后缀同理）

这一部分可以提前给每个串建立后缀自动机做到。

$cnt_i$ 的长度为 $\min(|s_i|,|s_k|)$，所以 $cnt$ 的总长是 $\mathcal{O}(n)$ 级别的。

对于询问，使用莫队来解决。正确排序的莫队复杂度为 $\mathcal{O}(n\sqrt{q})$。

总复杂度相当于

$A_1+A_2+\cdots A_{\frac{m}{B}}=q,\max\{\sum \sqrt{A_i}\}$。

视 $q,m$ 同阶，可以证明 $A_i$ 取 $B$ 时最优，复杂度为 $\mathcal{O}(\frac{mn}{B}\sqrt{B})$。

取 $B=n^{2/3}$ 得到最优复杂度 $\mathcal{O}(n^{5/3})$。