自动搬运

查看原文

来自洛谷，原作者为

	xhgua 如果只转身后退就能回到那个夏天

搬运于2025-08-24 22:36:54，当前版本为作者最后更新于2025-01-13 19:53:43，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

写一个复杂度较劣但是跑的挺快的做法。

首先建出 $s$ 的 AC 自动机，相当于求 $t_x$ 对应节点构成的虚树和 $t_y$ 对应节点构成的虚树的交集大小。

交集不好求，考虑用容斥原理转成求 $|T_x| + |T_y| - |T_x\cup T_y|$，即求虚树并。

首先我们考虑若知道 $t$ 在 AC 自动机上对应的节点 $u_1, u_2, \cdots u_k$，如何快速求出虚树的大小（即每个点到根对应链的并大小），沿用 P5840 Divljak 的做法，我们只需按 dfs 序排序后减去相邻两点 LCA 的贡献即可。不妨设 $|t_x| \leq |t_y|$，同样的，对于两个虚树的并，我们考虑将小串的节点插入大串中，具体地，我们对于小串的每个节点，二分找到它应该插在大串节点 dfn 序列的哪个位置，发现最多只会有 $\mathcal{O}(|t_x|)$ 个连续段，我们可以预处理这些连续段内部减去的贡献，并且加上插入时破坏的那部分大串的贡献即可，具体实现可以看代码。

这样子单次询问的时间复杂度即为 $\mathcal{O}(|t_x|\log |t_y|)$，如果对相同的询问记忆化，分析后可得总复杂度是 $\mathcal{O}(T\sqrt{q}\log T)$ 的，其中 $T$ 为 $\sum |t_i|$，已经可以通过本题。

不过我当时做题的时候并没有分析出这个复杂度，发现在 $|t_x|$ 和 $|t_y|$ 都很大时候这个做法较劣，考虑对 $t_x$ 的长度进行阈值分治。

令阈值为 $B$，当 $|t_x|\leq B$ 的时候我们跑上面那个做法，复杂度为 $\mathcal{O}(qB\log T)$，当 $|t_x| \gt B$ 时，这样的 $t$ 最多只有 $\mathcal{O}(\dfrac{T}{B})$ 个，我们考虑用 bitset 维护这些串是否包含 $s_i$，复杂度为 $\mathcal{O}(\dfrac{nT}{B})$，询问时直接把两个 bitset 与起来即可。

取 $B = \sqrt{\dfrac{nT}{q\log T}}$ 可得一个复杂度为 $\mathcal{O}(\sqrt{nqT\log T})$ 的做法，最慢点跑了 300ms。Code。