P5064

Cat_shao · 2022-09-08 13:59:27 · 题解

一种不需要树分块、时间复杂度 O(n \sqrt{n}) ，空间复杂度 O(n) 的做法。

（下文中的“元素”可理解为“数”“值”之类的）

大家先看 gyh20 的题解，我来简单复述下想法。考虑用值域分块求 kth ，离线所有操作，建出操作树，连边操作用可撤销并查集维护，每个并查集的根维护值域分块，记录每一个块中的元素个数（在这个集合内的）。这样 dfs 操作树，遇到询问的顶点，找到询问的连通块对应并查集的根，确定答案在哪个块，然后遍历块内元素，用并查集判断它们是否在询问的连通块中。这个做法时间空间复杂度均为 O(n \sqrt{n \log n}) ，跑得飞快（甚至比我们最终得到的做法还快）。

再看 zhylj 的题解，在前一种做法的基础上，逐块处理，对于每一个块都 dfs 一遍操作树，并查集的根记录所在集合中，在目前处理的块中的元素个数。每一次 dfs 操作树，并查集连边都得先找到两个集合的根，是 O(\log n) 的，再 O(1) 合并。因此我们先 dfs 一遍操作树，提前找到每一次连边操作中两个集合的根并存下来，接下来 dfs 就不用找根了。这个做法空间复杂度降到 O(n) ，且整块部分时间复杂度可视为 O(n \sqrt{n}) ，瓶颈在散块。

我们在 zhylj 的基础上稍加改进。并查集的根多维护一个链表，存有这个集合中的、在目前处理的块内的元素。合并两个链表是 O(1) 的，那么并查集合并仍是 O(1) ，撤销连边同理。对于散块，我们把（询问的连通块所在并查集的根的）链表誊到数组上，用 nth_element 求出 kth 。链表的长度是 O(\sqrt{n}) 的，进而散块部分的时间复杂度被加速到 O(n \sqrt{n}) 。

由此，我们得到了一种不需要树分块、时间复杂度 O(n \sqrt{n}) ，空间复杂度 O(n) 的做法。

如有疏漏，麻烦在评论区中指出。参考代码，实现请注意常数优化。