自动搬运

查看原文

来自洛谷，原作者为

	ppip work work

搬运于2025-08-24 22:28:51，当前版本为作者最后更新于2025-06-14 16:17:20，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

不要写，跑不过莫队二次离线。

假设 $n,q$ 同阶。

首先这个东西偏序逆序对，而逆序对归约矩乘，所以没有 polylog 做法。

首先我们注意到每个点能到达的点集能被拆成最多 $m+1$ 个子树，且这些子树都是某条额外边的出点或者自己。所以我们预处理一下每个点指向的点集即可。这部分可以做到 $O(nm)$。

反图上的到达点集同理，可以被拆成最多 $m+1$ 条不交路径。

接下来序列分块就是套路了，直接参考这个题的做法即可。

有很多拆贡献的方法，随便讲一种。

预处理：

• 两两块之间的答案；
• 前 $i$ 个块内的点在正反图上分别到达点 $j$ 的次数；
• 每个块内前后缀和的答案。

查询的时候：

• 如果 $l,r$ 同块则可以拆成两个块内前缀相减，以及两个散块的之间的贡献；
• 如果不同块则拆成中间整块的答案，两个散块内部的答案，中间整块到两边散块的贡献，两边散块之间的贡献。

预处理各种平衡一下，使用差分能轻松做到 $O(nm+n\sqrt{n})$。发现我们只有两个散块之间的贡献没有做。

这个不能直接归并，因为左侧散点的到达点集是 DFS 序上 $m$ 个区间，归并复杂度 $O(m\sqrt{n})$。

但是注意到大多数区间都是指定的 $m$ 条额外边的出点的子树，所以可以预处理右侧散块里每个指定的子树里有多少点，以及左侧有多少点包含指定子树，乘起来即可。剩下每个点到达的点集就是它的子树本身，直接归并扫一遍即可。

注意到以上做法居然需要 $O(n\sqrt{n})$ 的空间，太不牛了，但是每次询问只需要调用 $O(1)$ 个值所以离线逐块处理一下即可 $O(nm)$ 空间。

总复杂度 $O(nm+n\sqrt{n})$。