大家好，题解里很多大佬都是写的左偏树。

我很沙雕，所以我就来讲讲$\Huge\text{右}$偏树。 上面就是一棵右偏树（误）

原理

定义： 若一个节点有儿子是空的，那么这个节点就叫空节点。而一个节点的 $dis$ 值代表从这个节点出发，只经过左儿子到达一个空节点最少需要走的边数。

右偏树 的意思是：对于一棵树上的每一个节点，其右儿子的 $dis$ 值大于等于左儿子的 $dis$ 值。

若以 $u,v$ 为根的两个堆需要合并，由于已经维护好了右偏性质，所以只需要将 $v$ 合并到 $u$ 最左边的空节点，然后再递归维护右偏性质即可。

复杂度：很显然，在最坏情况下，由于堆的性质，当堆构成一颗完全树的时候 $dis[1]$ 到达 $logn$ ，合并操作依然能够维持在 $O(logn)$ ，是非常优秀的。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int n, m, heap[MAXN];
int fa[MAXN], ls[MAXN], rs[MAXN], dis[MAXN];
bool del[MAXN];

int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int Merge(int u, int v) {
    if (!u || !v)
        return u + v;
    if (heap[u] == heap[v] ? u > v : heap[u] > heap[v])
        swap(u, v); // 题目描述提到：优先删除原序列中靠前的
    ls[u] = Merge(ls[u], v); // 向左子树递归
    if (dis[ls[u]] > dis[rs[u]])
        swap(ls[u], rs[u]); // 维护右偏性质
    fa[ls[u]] = fa[rs[u]] = fa[u] = u; // 更新父亲
    dis[u] = dis[ls[u]] + 1;
    return u;
}

void pop(int u) {
    del[u] = true;
    fa[ls[u]] = ls[u];
    fa[rs[u]] = rs[u];
    // 先把左右儿子拆出去
    fa[u] = Merge(ls[u], rs[u]);
    // 然后合并为一个新堆
}

void init() {
    for (int i = 1; i <= n; i++)
        fa[i] = i;
}

int main() {
    dis[0] = -1;
    // 注意！此处是为了保证叶子节点 dis = 0
    scanf("%d %d", &n, &m);
    init();
    for (int i = 1; i <= n; i++)
        scanf("%d", &heap[i]);
    for (int opt, x, y; m; m--) {
        scanf("%d", &opt);
        if (opt == 1) {
            scanf("%d %d", &x, &y);
            if (del[x] || del[y])
                continue;
            x = find(x), y = find(y);
            if (x != y) 
                fa[x] = fa[y] = Merge(x, y);
        } else {
            scanf("%d", &x);
            if (del[x]) {
                printf("-1\n");
                continue;
            }
            x = find(x);
            printf("%d\n", heap[x]);
            pop(find(x));
        }
    }
    return 0;
}

如果你想看正经的左偏树该怎么写，也可以 看这里，你会发现怎么偏都没什么关系