题解：P15049 [UOI 2022 II Stage] 图 2

Xycxxx · 2026-01-25 21:51:42 · 题解

题目有回溯操作，考虑操作树。对于操作一和操作二，从上一个时间向当前时间连边。对于操作三，从回溯时间像当前时间连边，这样我们按操作树进行 dfs 可以保证到当前时间时所有的操作都是有效操作，即没有被回溯掉。

对于操作二，因为我们在操作树上 dfs 需要回溯，所以普通的权值线段树或者平衡树并不好维护，考虑对每个连通块维护一个值域分块求 kth，即从小到大遍历所有块，如果加上值在当前块中的数的个数依然 < k，则继续遍历，否则遍历当前块，维护每个值所在的连通块，并同上判断。注意要用并查集判断当前值是否为联通块内的。

对于操作一，如果两个点不连通，则需要合并两个连通块以及他们的根所对应的值域分块的信息。注意在操作树上回溯时要把当前操作撤销。可撤销并查集维护即可。

时间复杂度 \mathcal{O}(n\sqrt {n\log n})，但是常数极小，卡常后可以通过，块长要开大一点不然会空超。

代码卡常后很丑，有需可以私信。