题目地址：

https://www.acwing.com/problem/content/2716/

你需要维护一个小根堆的集合，初始时集合是空的。该集合需要支持如下四种操作：
1 a，在集合中插入一个新堆，堆中只包含一个数$a$。
2 x y，将第$x$个插入的数和第$y$个插入的数所在的小根堆合并。数据保证两个数均未被删除。若两数已在同一堆中，则忽略此操作。
3 x，输出第$x$个插入的数所在小根堆的最小值。数据保证该数未被删除。
4 x，删除第$x$个插入的数所在小根堆的最小值（若最小值不唯一，则优先删除先插入的数）。数据保证该数未被删除。

输入格式：
第一行包含整数$n$，表示总操作数量。
接下来$n$行，每行包含一个操作命令，形式如题所述。

输出格式：
对于每个操作$3$，输出一个整数，占一行，表示答案。

数据范围：
$1\le n\le 2\times 10^5$
$1\le a\le 10^9$
$1\le x,y\le$当前插入数的个数。
数据保证所有操作合法。

左偏树是一种可合并堆，其结构也是一棵二叉树，但不是像二叉堆那样的除了最后一层每一层都填满的二叉树，所以必须用链表形式存储。左偏树是这样一种二叉树数据结构（以最小堆为例）：
1、每个节点有两个值，权值和距离。每个节点的距离是指这个节点与与其最近的空节点的边数（空节点的距离定义为$0$）；
2、左偏树按照权值是一个最小堆；
3、每个节点的右儿子的距离小于等于左儿子的距离。

设$d[u]$是$u$节点的距离。设$f(k)$是当堆顶的距离为$k$的时候，整个堆的节点个数。我们证明$f(k)\ge 2^k-1$。$k=0,1$的时候显然成立。接下来数学归纳法，设$k\le n-1$的时候结论正确，当$k=n$的时候，设树根为$u$，左右儿子分别为$u_l,u_r$，那么 d [ u ] = min ⁡ { d [ u l ] , d [ u r ] } + 1 = d [ u r ] + 1 d[u]=\min\{d[u_l],d[u_r]\}+1=d[u_r]+1 d[u]=min{d[ul​],d[ur​]}+1=d[ur​]+1，所以其右儿子的节点个数大于等于$2^{n-1}+1$，而$d[u_l]\ge d[u_r]$，所以左儿子节点个数也大于等于$2^{n-1}+1$，所以总节点个数就大于等于$2^n+2-1=2^n-1$。

左偏树的核心操作是合并，即合并两个左偏树。合并方式如下：
1、如果其中一棵左偏树为空，则返回非空的那棵；
2、如果都不空，则合并递归进行。我们保证每次合并的时候，第一棵树的树根权值一定小于等于第二棵树的树根。合并的时候直接将第一棵树的右子树与第二个左偏树合并，合并完之后，回溯的时候看一下左右儿子的距离，如果右儿子距离大于左儿子距离，就交换两个儿子，同时更新一下当前节点的距离。最后返回第一棵树的树根。

合并两个左偏树的时间复杂度是$O(\log n)$的，$n$为两个左偏树节点数更大的那个的节点数。因为每次向下递归一次都是在合并第一棵左偏树的右子树和第二棵左偏树，所以每次向下一层，处理的节点数就会减半，从而总复杂度是$O(\log n)$。也可以这么想，如果整个堆的节点数为$n$，则树根的距离为$O(\log n)$，由于每次都是合并右子树，所以递归层数即时间复杂度是$O(\log n)$。

由于要迅速找到每个节点所在堆的堆顶，我们需要开一个并查集来维护堆中的元素。合并的时候也要合并并查集。接下来考虑题目中的操作如何做：
1、插入一个新堆，新堆只含一个数$a$：直接开一个新节点即可，并查集也开一个新集合；
2、将第$x$个插入的数和第$y$个插入的数所在的堆合并，若两个数在同一堆中则忽略：我们保证每个并查集内部，每个节点的树根在堆里也是堆顶。那么先在并查集里找到$x$和$y$的树根，如果树根不一样则需要做合并，不妨设$x$即为树根，$y$也是树根，不妨设$x$的权值不大于$y$的权值，则开始做合并，并在并查集里让$p[y]=x$；
3、输出第$x$个插入的数所在堆的最小值：即输出堆顶，通过并查集找到树根，直接输出树根权值；
4、删除第$x$个插入的数所在的堆的最小值，若存在多个则删除下标最小的：这一点的实现需要我们在合并的操作里，当堆顶相等的时候，让下标较小的当堆顶。这样就可以先找到最小值的节点下标，在并查集里我们不真的删之，而是将这个树根的父亲连到左儿子处，让左儿子成为其所在集合的新树根。接着直接合并左右子堆即可。

代码如下：

#include 
using namespace std;

const int N = 2e5 + 10;
int n;
int v[N], dist[N], l[N], r[N], idx;
int p[N];

// 比较x和y这两个节点在合并的时候哪个更适合做堆顶
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];
}

// 合并x和y两个节点
int merge(int x, int y) {
  // 一个堆为空，则返回非空的那个堆
  if (!x || !y) return x ^ y;
  // 让x是更适合做堆顶的节点
  if (!cmp(x, y)) swap(x, y);
  // 将x的右子堆和y合并，并维护左偏树的距离性质
  r[x] = merge(r[x], y);
  if (dist[r[x]] > dist[l[x]]) swap(l[x], r[x]);
  // 更新合并完成后的树根x的距离
  dist[x] = dist[r[x]] + 1;
  return x;
}

int main() {
  scanf("%d", &n);
  // 让空节点权值无穷大，理由见下面操作4
  v[0] = 2e9;

  while (n--) {
    int t, x, y;
    scanf("%d%d", &t, &x);
    if (t == 1) {
      v[++idx] = x;
      p[idx] = idx;
      dist[idx] = 1;
    } else if (t == 2) {
      scanf("%d", &y);
      x = find(x), y = find(y);
      if (x != y) {
        if (!cmp(x, y)) swap(x, y);
        p[y] = x;
        merge(x, y);
      }
    } else if (t == 3) printf("%d\n", v[find(x)]);
    else {
      x = find(x);
      // 为了方便，我们这里不去判断x的左右儿子是否为空，而
      // 直接让空节点权值无穷大，这样空节点永远不会成为树根
      if (!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
64
65
66

设$n$为当前已经插入了多少个数，操作$1$时间复杂度$O(1)$，操作$2$和$4$时间$O(\log n)$，操作$3$时间$O({\log }^{\ast }n)$，总空间$O(n)$。