题解：P15049 [UOI 2022 II Stage] 图 2
前言套路题。
目前是双倍经验的最优解和这个题的最优解。
思路
发现有回溯操作，考虑经典转化建出操作树变成可撤销问题，因为有连边操作，所以使用可撤销并查集维护连通性。
维护第 \(k\) 大，我们通常使用值域分块解决，考虑对每个并查集的根维护所在集合内的答案。在可撤销并查集合并的时候合并答案，类似于启发式合并。这样复杂度是 \(O(n\sqrt{n \log n})\)，可以通过。
具体实现可以看代码。
代码
constexpr int N = 5e5 + 2;int n, m, A, B, fa, g, siz, ans, typ, D, K, cnt;int f;int p, hd, to; if(typ == 1) cin >> A >> B, add(i - 1, i); else if(typ == 2) cin >> A >> B, add(i - 1, i); else cin >> A, add(A, i); } dfs(0); for(int i = 1; i 感谢分享，下载保存了，貌似很强大
页:
[1]