P7331 Dream and the Multiverse REMATCH 题解

ppip · 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})。