左偏树

他必像牧人牧养自己的羊群，用膀臂聚集羊羔抱在怀中，慢慢引导那乳养小羊的。

左偏树

左偏树属于可并堆，在统计、最值、模拟、贪心等类型的题目中应用广泛。

在左偏树中我们关心每个节点的势能，即每个点到其子树中深度最小的外节点的距离（外节点：左右儿子不全的节点）。如果一个点的势能是 ，那么从这个点开始往下的 层都是满的，至少拥有 个点，所以对于一颗左偏树，就势能而言是 级别的。所以每个点的势能，其实就是以该点为根的子树中，最右边那条链的长度。考虑递归合并操作，假设我们现在要合并根 rt1 和 rt2 ，如果 rt1 要成为 rt2 的父节点，那么就把 rt2 和 rt1 -> rs （rt1 的右儿子）进行合并，递归结束后，如果 rt1 左儿子的势能比右儿子的势能小，就交换左右儿子，如是可知，每次递归会让某一个堆的势能 -1 ，所以合并操作的复杂度是 rt1 和 rt2 的势能和，是 级别的，优秀子。而删除操作和加点操作都可以借由合并操作完成。

板子题

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

一开始有 个小根堆，每个堆包含且仅包含一个数。接下来需要支持两种操作：

1 x y：将第 个数和第 个数所在的小根堆合并（若第 或第 个数已经被删除或第 和第 个数在用一个堆内，则无视此操作）。

2 x：输出第 个数所在的堆最小数，并将这个最小数删除（若有多个最小数，优先删除先输入的；若第 个数已经被删除，则输出 并无视删除操作）。

思路：用并查集维护堆的合并情况；son[u][0] 和 son[u][1] 分别存左二子和右儿子的编号，用于建树；dis 用于维护势能；

#include<bits/stdc++.h>
using namespace std;

inline int rd() {
   int x = 0; bool f = 0; char c = getchar();
   for (; !isdigit(c); c = getchar()) f |= (c == '-');
   for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
   return f ? -x : x;
}

#define N 100007
bool invalid[N];
int son[N][2], f[N], dis[N], w[N];

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

int merge(int rt1, int rt2) {
    if (!rt1 || !rt2) return rt1 | rt2;
    // rt1 be the root
    if (w[rt1] > w[rt2] || (w[rt1] == w[rt2] && rt1 > rt2)) swap(rt1, rt2);
    int ls = son[rt1][0], rs = son[rt1][1];
    rs = merge(rs, rt2); son[rt1][1] = rs;
    if (dis[ls] < dis[rs]) {swap(ls, rs); swap(son[rt1][0], son[rt1][1]);}
    f[ls] = f[rs] = rt1;
    dis[rt1] = dis[rs] + 1;
    return rt1;
}

inline int del(int x) {
    invalid[x] = 1;
    int ls = son[x][0], rs = son[x][1];
    f[ls] = f[rs] = f[x] = merge(ls, rs); // 一个点哪怕被删掉了，但还是留用它，用于并查集维护合并情况
    return w[x];
}

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) {w[i] = rd(); f[i] = i;}
    for (int i = 1; i <= m; ++i) {
        int op = rd();
        if (op == 1) {
            int x = rd(), y = rd();
            if (invalid[x] || invalid[y]) continue;
            if (find(x) != find(y)) merge(find(x), find(y));
        } else {
            int x = rd();
            if (invalid[x]) puts("-1");
            else printf("%d\n", del(find(x)));
        }
    }
    return 0;
}