前言
套路题。
目前是双倍经验的最优解和这个题的最优解。
思路
发现有回溯操作，考虑经典转化建出操作树变成可撤销问题，因为有连边操作，所以使用可撤销并查集维护连通性。
维护第 \(k\) 大，我们通常使用值域分块解决，考虑对每个并查集的根维护所在集合内的答案。在可撤销并查集合并的时候合并答案，类似于启发式合并。这样复杂度是 \(O(n\sqrt{n \log n})\)，可以通过。
具体实现可以看代码。
代码
constexpr int N = 5e5 + 2;
int n, m, A[N], B[N], fa[N], g, siz[N], ans[N], typ[N], D, K, cnt;
int f[N][810];
int p[N], hd[N], to[N << 1], nxt[N << 1];
inline void add(int u, int v){ nxt[++cnt] = hd[u], to[cnt] = v, hd[u] = cnt;}
inline int find(int x){ return x == fa[x] ? x : find(fa[x]);}
inline void dfs(int u){bool flag = 0;if(typ[u] == 2){A[u] = find(A[u]), B[u] = find(B[u]);if(A[u] ^ B[u]){flag = 1;if(siz[A[u]] < siz[B[u]]) swap(A[u], B[u]);siz[A[u]] += siz[B[u]], fa[B[u]] = A[u];for(int i = 1; i <= K; ++i) f[A[u]][i] += f[B[u]][i];}}else if(typ[u] == 1){int s = B[u], rt = find(A[u]), y = 0; if(s > siz[rt]) ans[u] = -1;else{for(int i = 1; i <= K && !y; i++) s > f[rt][i] ? s -= f[rt][i] : y = i;for(int i = (y - 1) * D + 1; i <= y * D && s; ++i) if(find(p[i]) == rt) --s, ans[u] = p[i];}}for(int i = hd[u]; i; i = nxt[i]) dfs(to[i]);if(flag){siz[A[u]] -= siz[B[u]], fa[B[u]] = B[u];for(int i = 1; i <= K; ++i) f[A[u]][i] -= f[B[u]][i];}
}
int main(){#ifndef ONLINE_JUDGEfreopen("data.in","r",stdin);freopen("data.out","w",stdout);#endifcin >> n >> m >> g; D = sqrt(n) * 1.5 + 1, K = (n - 1) / D + 1;for(int i = 1; i <= n; ++i) p[i] = i, siz[fa[i] = i] = 1, ++f[i][(i - 1) / D + 1];for(int i = 1; i <= m; ++i){cin >> typ[i];if(typ[i] == 1) cin >> A[i] >> B[i], add(i - 1, i);else if(typ[i] == 2) cin >> A[i] >> B[i], add(i - 1, i);else cin >> A[i], add(A[i], i);} dfs(0);for(int i = 1; i <= m; ++i) if(typ[i] == 1) cout << ans[i] << '\n';return 0;
}