自动搬运

查看原文

来自洛谷，原作者为

	mrsrz 故障机器人

搬运于2025-08-24 22:23:55，当前版本为作者最后更新于2020-10-12 09:28:59，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

rplexq = range pair LCA equal x query

这题就是各种平衡复杂度。

考虑朴素的做法。对 $x$ 的每棵子树统计它里面编号在 $[l,r]$ 内的节点个数，然后计算两两乘积的和。可以通过总节点数平方减去每个儿子子树里节点平方的方式计算。

考虑对节点度数进行根号分治。

• 对于儿子数小于等于 $\sqrt n$ 的 $x$，我们想办法对 $x$ 的每个询问都求出所有子树中编号在 $[l,r]$ 内的节点个数，然后计算答案。

  容易发现，我们相当于在做一个 $O(n)$ 个点，$O(m\sqrt n)$ 个询问的二维数点问题。

  为了平衡两边的复杂度，我们只需要使用分块前缀和的方式进行维护，这样单次修改 $O(\sqrt n)$，单次查询 $O(1)$。那么二维数点部分的总时间复杂度为 $O((n+m)\sqrt n)$。

  但是要存下所有的询问，需要 $O(m\sqrt n)$ 的空间复杂度。注意到对于一个 $x$ 的所有询问，它们所需要查询的子树都是一样的，而且 dfs 序区间连续且互不相交。因此我们数点时不具体记录每个询问，而是记录 $x$，处理时对这个 $x$ 计算答案。于是空间复杂度 $O(n+m)$。

• 对于儿子数大于 $\sqrt n$ 的节点 $x$，这样的 $x$ 不超过 $\sqrt n$ 个。由于节点度数可能很大，因此我们不能逐个儿子进行查询。

  考虑枚举 $x$ 每个儿子 $v$，并遍历 $v$ 所在子树，将子树中的节点都标记上 $v$。然后对于每个询问，我们考虑求出不合法的方案，即每棵子树内节点的平方和。容易发现这是一个经典的问题——小 Z 的袜子，可以使用莫队算法求解。

  遍历节点的总复杂度是 $O(n\sqrt n)$ 没有问题，但是对于一个节点 $i$，莫队算法的复杂度是 $O(n_i\sqrt {m_i})$，而 $n_i$ 的总和可以达到 $n\sqrt n$，因此是错误的。

  我们希望 $n_i$ 的总和为 $n$，这样总的复杂度就为 $O(\sum n_i\sqrt{m_i})\leq O(\sum n_i\sqrt m)=O(n\sqrt m)$。

  考虑按 dfs 顺序处理询问，保证 $x$ 处理的时候，$x$ 子树中需要处理询问的节点均已处理完毕。

  在遍历节点时，我们分开记录之前的询问没遍历过的节点，和之前的询问遍历过的节点。

  对于之前询问没遍历的节点，我们将它放到序列上，对 $x$ 的询问，在这个序列上离散化后进行莫队。这样序列的总长度为 $O(n)$，则莫队的复杂度为 $O(n\sqrt m)$。

  对于之前询问遍历过的节点，我们对 $x$ 的每个儿子节点开一个数据结构，支持快速区间求和。由于我们在最开始进行了根号分治，因此存在之前询问遍历过的节点的儿子不超过 $\sqrt n$ 个，所以只需要对这些儿子开数据结构即可。

  由于每个询问要查询这 $\sqrt n$ 个儿子的信息，因此需要 $O(1)$ 的查询。想要做到 $O(1)$ 的查询则容易想到使用分块。朴素的做法对每个儿子开 $\sqrt n$ 大小的数组用于统计每个块内的节点个数，空间是可以承受的，但是还需要 $O(n)$ 大小的数组用于统计每个点的出现次数，这是无法承受的。注意到每个编号的点只有一个，因此我们可以直接开一个数组存这个点是否出现。空间复杂度 $O(n)$。

  这部分处理完以后，对分块数组进行前缀和统计，即可 $O(1)$ 查询块的区间和。

  在处理询问的时候，对于之前询问没遍历过的节点，它们的信息通过莫队算法得到。对于之前询问遍历过的节点，我们对每个儿子分别统计：块间的只需要 $O(1)$ 做块差分即可，共查询 $O(\sqrt n)$ 次，时间复杂度 $O(\sqrt n)$。边角的我们直接枚举，并对相应计数器加一，时间复杂度 $O(\sqrt n)$。然后再把这些儿子多出来的贡献加上去，时间复杂度 $O(\sqrt n)$。所以总时间复杂度 $O(m\sqrt n)$。

如果之前统计的是不合法方案，最后还需要一次二维数点来统计总方案。时间复杂度为 $O(m\log n)$。

综上，这个算法的时间复杂度为 $O(n\sqrt n+n\sqrt m+m\sqrt n)$，空间复杂度 $O(n+m)$。