题目地址：

https://www.luogu.com.cn/problem/P3377

题目描述：
如题，一开始有$n$个小根堆，每个堆包含且仅包含一个数。接下来需要支持两种操作：
1、1 x y：将第$x$个数和第$y$个数所在的小根堆合并（若第$x$或第$y$个数已经被删除或第$x$和第$y$个数在用一个堆内，则无视此操作）。
2、2 x：输出第$x$个数所在的堆最小数，并将这个最小数删除（若有多个最小数，优先删除先输入的；若第$x$个数已经被删除，则输出$-1$并无视删除操作）。

输入格式：
第一行包含两个正整数$n,m$，分别表示一开始小根堆的个数和接下来操作的个数。
第二行包含$n$个正整数，其中第$i$个正整数表示第$i$个小根堆初始时包含且仅包含的数。
接下来$m$行每行$2$个或$3$个正整数，表示一条操作，格式如下：
操作$1$：1 x y
操作$2$：2 x

输出格式：
输出包含若干行整数，分别依次对应每一个操作$2$所得的结果。

数据范围：
对于$30\%$的数据：$n\le 10$，$m\le 10$。
对于$70\%$的数据：$n\le 10^3$，$m\le 10^3$。
对于$100\%$的数据：$n\le 10^5$，$m\le 10^5$，初始时小根堆中的所有数都在int范围内。

参考https://blog.csdn.net/qq_46105170/article/details/126204599。可以将删除了的点的距离值$d$设为$0$。代码如下：

#include 
using namespace std;

const int N = 1e5 + 10;
int n, m;
int v[N], d[N], l[N], r[N];
int p[N];

bool cmp(int x, int y) {
  if (v[x] != v[y]) return v[x] < v[y];
  return x < y;
}

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

int merge(int x, int y) {
  if (!x || !y) return x ^ y;
  if (!cmp(x, y)) swap(x, y);
  r[x] = merge(r[x], y);
  if (d[r[x]] > d[l[x]]) swap(l[x], r[x]);
  d[x] = d[r[x]] + 1;
  return x;
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    p[i] = i;
    d[i] = 1;
    scanf("%d", &v[i]);
  }

  while (m--) {
    int t, x, y;
    scanf("%d%d", &t, &x);
    if (t == 1) {
      scanf("%d", &y);
      if (!d[x] || !d[y]) continue;
      x = find(x), y = find(y);
      if (x == y) continue;
      if (!cmp(x, y)) swap(x, y);
      p[y] = x;
      merge(x, y);
    } else {
      if (!d[x]) {
        puts("-1");
        continue;
      }
      x = find(x);
      printf("%d\n", v[x]);
      // 标记x为已经被删除
      d[x] = 0;
      // 如果x不是叶子，并且左儿子更适合做堆顶（值小或者值等下标小），则交换左右儿子，
      // 这是为了防止空节点被换到左边
      if (r[x] && !cmp(l[x], r[x])) swap(l[x], r[x]);
      p[x] = p[l[x]] = l[x];
      merge(l[x], r[x]);
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

每次操作时间复杂度$O(\log n)$，空间$O(n)$。