题面
永无乡包含 \(n\) 座岛，编号从 \(1\) 到 \(n\) ，每座岛都有自己的独一无二的重要度，按照重要度可以将这 \(n\) 座岛排名，名次用 \(1\) 到 \(n\) 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛 \(a\) 出发经过若干座（含 \(0\) 座）桥可以 到达岛 \(b\) ，则称岛 \(a\) 和岛 \(b\) 是连通的。
现在有两种操作：
B x y 表示在岛 \(x\) 与岛 \(y\) 之间修建一座新桥。
Q x k 表示询问当前与岛 \(x\) 连通的所有岛中第 \(k\) 重要的是哪座岛，即所有与岛 \(x\) 连通的岛中重要度排名第 \(k\) 小的岛是哪座，请你输出那个岛的编号。
题解
为什么我的\(splay\)这么慢?
线段树合并好像可以做
不过练练平衡树合并也行
合并时启发式合并
复杂度\(O(nlog^2n)\)
Code
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
struct node {
int ch[2], v, f, s, id;
}t[N*30];
int root[N], tot;
void pushup(int x) {
t[x].s = t[t[x].ch[0]].s + t[t[x].ch[1]].s + 1;
}
void rotate(int x) {
int y = t[x].f, z = t[y].f, k = t[y].ch[1] == x;
t[z].ch[t[z].ch[1] == y] = x; t[x].f = z;
t[y].ch[k] = t[x].ch[k^1]; t[t[x].ch[k^1]].f = y;
t[y].f = x; t[x].ch[k^1] = y;
pushup(y);
}
void splay(int x, int goal, int k) {
while (t[x].f != goal) {
int y = t[x].f, z = t[y].f;
if (z != goal)
(t[y].ch[1] == x) ^ (t[z].ch[1] == y) ? rotate(x) : rotate(y);
rotate(x);
}
pushup(x);
if (!goal) root[k] = x;
}
void insert(int k, int x, int id) {
int now = root[k], f = 0;
while (now) f = now, now = t[now].ch[x > t[now].v];
now = ++tot;
t[f].ch[x > t[f].v] = now;
t[now].f = f; t[now].v = x; t[now].id = id;
splay(now, 0, k);
}
int kth(int k, int x) {
int now = root[k];
while (1) {
int ls = t[now].ch[0], rs = t[now].ch[1];
if (t[ls].s >= x) now = ls;
else if (t[ls].s + 1 < x) now = rs, x -= (t[ls].s + 1);
else return t[now].id;
}
}
int n, m;
int fa[N], a[N];
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void dfs(int x, int y) {
insert(x, t[y].v, t[y].id);
if (t[y].ch[0]) dfs(x, t[y].ch[0]);
if (t[y].ch[1]) dfs(x, t[y].ch[1]);
return ;
}
void merge(int a, int b) {
if (a == b) return ;
if (t[root[a]].s < t[root[b]].s) swap(a, b);
fa[b] = a;
dfs(a, root[b]);
}
void deb(int x) {
if (t[x].ch[0]) deb(t[x].ch[0]);
printf("%d ", t[x].v);
if (t[x].ch[1]) deb(t[x].ch[1]);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) fa[i] = i, scanf("%d", &a[i]);
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%d%d", &x, &y);
x = find(x), y = find(y);
fa[y] = x;
}
for (int i = 1; i <= n; i++) {
int x = find(i);
insert(x, a[i], i);
}
int Q;
scanf("%d", &Q);
while (Q--) {
char c; int a, b;
cin >> c >> a >> b;
if (c == 'Q') {
a = find(a);
/*printf("test : ");
deb(root[a]);
printf("\n");*/
if (t[root[a]].s < b) puts("-1");
else printf("%d\n", kth(a, b));
}
else {
a = find(a), b = find(b);
merge(a, b);
}
}
return 0;
}