题目大意：有$n$个数，$m$个操作：
- $1\;x\;y：$把第$x$个数和第$y$个数所在的小根堆合并
- $2\;x：$输出第$x$个数所在的堆的最小值
题解：左偏树，保证每个的左儿子的距离大于右儿子（距离的定义是该点到其子树中最近的叶子节点的距离）
卡点：无
C++ Code：
#include <cstdio>
#include <algorithm>
#define maxn 100010
int n, m;
int val[maxn];
int fa[maxn], lc[maxn], rc[maxn], dis[maxn];
inline int find(int x) {while (fa[x]) x = fa[x]; return x;}
int merge(int x, int y) {
if (!x || !y) return x | y;
if ((val[x] > val[y]) || (val[x] == val[y] && x > y)) std::swap(x, y);
rc[x] = merge(rc[x], y); fa[rc[x]] = x;
if (dis[rc[x]] > dis[lc[x]]) std::swap(lc[x], rc[x]);
dis[x] = dis[rc[x]] + 1;
return x;
}
int pop(int x) {
fa[lc[x]] = fa[rc[x]] = 0;
merge(lc[x], rc[x]);
int tmp = val[x]; val[x] = -1;
return tmp;
}
int main() {
scanf("%d%d", &n, &m); dis[0] = -1;
for (int i = 1; i <= n; i++) scanf("%d", val + i);
for (int i = 1; i <= m; i++) {
int op, x, y;
scanf("%d%d", &op, &x);
if (op == 1) {
scanf("%d", &y);
int __x = find(x), __y = find(y);
if (~val[x] && ~val[y] && __x != __y) merge(__x, __y);
} else {
if (~val[x]) printf("%d\n", pop(find(x)));
else puts("-1");
}
}
return 0;
}