传送门
并查集+Splay+启发式合并
启发式合并:
每次合并两个Splay时,将节点数小的合并至节点数大的。
神奇的时间复杂度:完成所有的合并总共\(O(N\log{N})\),然而不会证。此题合并平衡树,则为\(O(N\log^2{N})\)。
其他没什么了。
#include<cstdio> #include<algorithm> using namespace std; const int N = 1e5 + 5; struct Splay { int s[2], p, val, size; void init(int _v, int _p) { val = _v; p = _p; size = 1; } } a[N]; int n, m, r[N], root[N]; int fa[N], sz[N]; int get(int x) { if (x == fa[x]) return x; return fa[x] = get(fa[x]); } void pushup(int x) { a[x].size = a[a[x].s[0]].size + a[a[x].s[1]].size + 1; } void rotate(int x) { int y = a[x].p, z = a[y].p, k = a[y].s[1] == x; a[z].s[a[z].s[1] == y] = x; a[x].p = z; a[y].s[k] = a[x].s[k ^ 1]; a[a[x].s[k ^ 1]].p = y; a[x].s[k ^ 1] = y; a[y].p = x; pushup(y); pushup(x); } void Splay(int x, int k, int rt) { while (a[x].p != k) { int y = a[x].p, z = a[y].p; if (z != k) { if (a[y].s[1] == y ^ a[y].s[1] == x) rotate(x); else rotate(y); } rotate(x); } if (!k) root[rt] = x; } void Insert(int x, int rt) { int p = root[rt], q = 0; while (p) { q = p; p = a[p].s[a[x].val > a[p].val]; } a[x].init(a[x].val, q); a[q].s[a[x].val > a[q].val] = x; Splay(x, 0, rt); } void Transfer(int p, int rt) { if (!p) return ; Transfer(a[p].s[0], rt); Transfer(a[p].s[1], rt); Insert(p, rt); } void Merge(int x, int y) { if (sz[x] > sz[y]) swap(x, y); fa[x] = y; sz[y] += sz[x]; Transfer(root[x], y); } int Get_K(int x, int k) { int p = root[x]; while (p) { if (a[a[p].s[0]].size >= k) p = a[p].s[0]; else if (a[a[p].s[0]].size + 1 == k) return p; else { k -= a[a[p].s[0]].size + 1; p = a[p].s[1]; } } return -1; } int main() { char opt[5]; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &r[i]); a[i].init(r[i], 0); fa[i] = i; sz[i] = 1; root[i] = i; } while (m--) { int x, y; scanf("%d%d", &x, &y); Merge(x, y); } int q; scanf("%d", &q); while (q--) { int x, y; scanf("%s%d%d", opt, &x, &y); if (opt[0] == 'B') Merge(get(x), get(y)); else printf("%d\n", Get_K(get(x), y)); } return 0; }