```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n, m;
bool deleted[MAXN];
struct LeftistHeap {
struct Node {
int value, id, dist, left, right;
bool operator<(const Node &other) const {
return value < other.value || (value == other.value && id < other.id);
}
};
Node heap[MAXN];
int parent[MAXN];
LeftistHeap() {
heap[0].dist = -1; // 初始化空节点
for (int i = 0; i < MAXN; ++i) parent[i] = i;
}
int findRoot(int x) {
if (parent[x] != x) parent[x] = findRoot(parent[x]);
return parent[x];
}
int merge(int x, int y) {
if (!x || !y) return x + y;
if (heap[y] < heap[x]) swap(x, y);
heap[x].right = merge(heap[x].right, y);
if (heap[heap[x].right].dist > heap[heap[x].left].dist)
swap(heap[x].left, heap[x].right);
heap[x].dist = heap[heap[x].right].dist + 1;
return x;
}
void pop(int x) {
deleted[x] = true;
int root = findRoot(x);
int new_root = merge(heap[root].left, heap[root].right);
parent[heap[root].left] = parent[heap[root].right] = new_root;
parent[root] = new_root;
heap[root] = Node{0, 0, 0, 0, 0}; // 重置删除的节点
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
LeftistHeap lh;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> lh.heap[i].value;
lh.heap[i].id = i;
}
while (m--) {
int op, x, y;
cin >> op >> x;
if (op == 1) {
cin >> y;
if (!deleted[x] && !deleted[y]) {
x = lh.findRoot(x);
y = lh.findRoot(y);
if (x != y) lh.parent[x] = lh.parent[y] = lh.merge(x, y);
}
} else {
if (deleted[x]) {
cout << -1 << '\n';
continue;
}
x = lh.findRoot(x);
cout << lh.heap[x].value << '\n';
lh.pop(x);
}
}
return 0;
}
```
@[huays1230](/user/538761) 我个人习惯不太喜欢用 `namespace` 命名一个新空间。可读性不太高(
优化了一下你的查找根节点的逻辑,相对更简洁了些。
by Zemu_Ooo @ 2024-01-02 22:37:24
@[Zemu_Ooo](https://www.luogu.com.cn/user/467824)非常感谢
by huays1230 @ 2024-01-03 18:44:31