P8203 DDOSvoid 的馈赠 题解

· · 题解

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

首先建出 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。