P15049 [UOI 2022 II Stage] 图 2 题解

· · 题解

前言：

我常常追忆过去。

神必，使用 bitset 把两个题最优解都拱掉了。

思路：

以下默认 n,m 同阶。

首先看到要求图上可达点最小值，很容易联想到 P11831 [省选联考 2025] 追忆。于是考虑如何用 bitset 做。初步考虑：对于每个点维护一个 bitset，第 i 位记录是否可达 i。

查询的话，相当于对于一个 bitset 查询第 k 个 1 的位置。手写 bitset 进行统计即可，单次时间复杂度 O(\dfrac{n}{w})。

连接两个点的话，并查集启发式合并 fa 处的两个 bitset 即可，单次时间复杂度 O(\dfrac{n}{w})。

有回溯操作的话，考虑将所有操作建成一棵操作树，那么进行 dfs 遍历，遍历到的时候更新，退出的时候将贡献复原即可。

因为并查集需要撤销操作，所以不能进行路径压缩，需要启发式合并保证复杂度。

这样总时间复杂度是 O(\dfrac{n^2}{w}) 的，但是空间复杂度也是 O(\dfrac{n^2}{w})，开不下。这部分的代码。

考虑如何优化。类似于 CF1641D Two Arrays 的想法，那题是进行根号分治，如果出现次数 <S 就直接暴力，这样空间复杂度是 O(n) 的。

那么这题也是一样，设置一个阈值，如果并查集上当前节点的 sz<S 就暴力维护一个链表；如果 sz \ge S 就维护 bitset。当 S\leftarrow \dfrac{n}{w} 时空间复杂度就是 O(n) 的（当然如果你是在做 Ynoi 那个题可能还得调调这个 S）。

求链表第 k 小可以使用 nth_element 或者手写类似于快排的东西。

合并的话，如果是一个 bitset 和一个链表，遍历链表给 bitset 赋值即可（启发式合并可以保证复杂度）。如果是两个链表，首尾相接即可。合并后如果大小达到了 S 存入 bitset 即可。

分裂同理。

Ynoi 那个题空间比较恶心可能还需要写回收池。

代码。

我该在哪里停留？我问我自己。