P3224 [HNOI2012] 永无乡

题意

思路

用并查集维护连通性，每个集合维护一个平衡树，每次合并两个集合的时候，将一个平衡树的节点一个一个加入到另一个中。

这么做不会超时，每次将小的平衡树拆掉放到大的中，可以证明不会超过 \(O(\log n)\) 次。

总时间复杂度 \(O(n \log ^ 2 n)\)。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1000010;

struct node {
	int l, r;
	int size;
	int rnd;
	int key;
	int x;
} tr[N];

int rt[N], idx;

void pushup(int u) {
	tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + 1;
}

void split(int u, int key, int& x, int& y) {
	if (!u) {
		x = y = 0;
		return;
	}
	if (tr[u].key <= key) {
		x = u;
		split(tr[u].r, key, tr[u].r, y);
	}
	else {
		y = u;
		split(tr[u].l, key, x, tr[u].l);
	}
	pushup(u);
}

int merge(int x, int y) {
	if ((!x) || (!y)) return x | y;
	if (tr[x].rnd < tr[y].rnd) {
		tr[x].r = merge(tr[x].r, y);
		pushup(x);
		return x;
	}
	else {
		tr[y].l = merge(x, tr[y].l);
		pushup(y);
		return y;
	}
}

int newnode(int key, int x) {
	idx++;
	tr[idx].key = key;
	tr[idx].rnd = rand();
	tr[idx].size = 1;
	tr[idx].l = tr[idx].r = 0;
	tr[idx].x = x;
	return idx;
}

void insert(int& rt, int key, int g) {
	int x, y;
	split(rt, key, x, y);
	int z = newnode(key, g);
	rt = merge(merge(x, z), y);
}

int fa[N];

int find(int x) {
	if (x == fa[x]) return x;
	return fa[x] = find(fa[x]);
}

void merge_fa(int x, int y) {
	x = find(x), y = find(y);
	if (x == y) return;
	if (tr[rt[x]].size > tr[rt[y]].size) swap(x, y);
	fa[x] = y;
	
	queue<int> q;
	q.push(rt[x]);
	while (q.size()) {
		int t = q.front();
		q.pop();
		insert(rt[y], tr[t].key, tr[t].x);
		if (tr[t].l) q.push(tr[t].l);
		if (tr[t].r) q.push(tr[t].r);
	}
}

int get_rank(int u, int rk) {
	if (tr[tr[u].l].size + 1 == rk) return tr[u].x;
	if (tr[tr[u].l].size >= rk) return get_rank(tr[u].l, rk);
	return get_rank(tr[u].r, rk - tr[tr[u].l].size - 1);
}

int n, m;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		insert(rt[i], x, i);
		fa[i] = i;
	}
	
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		merge_fa(u, v);
	}
	int q;
	cin >> q;
	char opt;
	int x, y;
	while (q--) {
		cin >> opt >> x >> y;
		if (opt == 'Q') {
			x = find(x);
			if (tr[rt[x]].size < y) cout << "-1\n";
			else cout << get_rank(rt[x], y) << '\n';
		}
		else merge_fa(x, y);
	}
	return 0;
}