【数据结构】左偏树

验证链接：左偏树：https://www.luogu.com.cn/problem/P3377
验证链接：堆：https://www.luogu.com.cn/problem/P3378

维护一种数据结构，支持下列操作：

插入新元素到某个集合中
查询某个集合中的最小元素
删除某个集合中的最小元素
合并两个集合

在这个问题中，操作1~操作3是堆的正常操作，这里多了一个操作3，所以要实现的是一个可并堆。

对上面这个问题进行明确：

维护一种数据结构，支持下列操作：

插入新元素val到某个集合S_i中
查询某个集合S_i中的最小元素
删除某个集合S_i中的最小元素
合并两个集合S_i和S_j，合并后S_i和S_j都指向新的集合

发现这个实际上需要结合并查集去做，利用并查集快速找到每个集合编号当前对应的新集合。新元素直接单独变成一个新集合，操作1归约到操作4。

struct LeftistTree {

    static const int MAXN = 2e5 + 10;

    int lch[MAXN], rch[MAXN];
    int val[MAXN], dis[MAXN];
    int fnd[MAXN], del[MAXN];

    int _Find(int x) {
        return (fnd[x] == x) ? x : fnd[x] = _Find(fnd[x]);
    }

    int _Merge(int x, int y) {
        if(x == 0 || y == 0)
            return x + y;
        if(val[x] > val[y] || val[x] == val[y] && x > y)
            swap(x, y);
        rch[x] = _Merge(rch[x], y);
        if(dis[lch[x]] < dis[rch[x]])
            swap(lch[x], rch[x]);
        fnd[x] = x, fnd[lch[x]] = x, fnd[rch[x]] = x;
        dis[x] = dis[rch[x]] + 1;
        return x;
    }

    void Init(int *a, int n) {
        for(int i = 1; i <= n; ++i) {
            lch[i] = 0, rch[i] = 0;
            val[i] = a[i], dis[i] = 0;
            fnd[i] = i, del[i] = 0;
        }
    }

    void Merge(int x, int y) {
        if(del[x] == 1 || del[y] == 1)
            return;
        x = _Find(x), y = _Find(y);
        if(x == y)
            return;
        _Merge(x, y);
    }

    int Top(int x) {
        if(del[x] == 1)
            return -1;
        x = _Find(x);
        return val[x];
    }

    void Pop(int x) {
        if(del[x] == 1)
            return;
        x = _Find(x);
        del[x] = 1;
        int r = _Merge(lch[x], rch[x]);
        fnd[x] = r, fnd[lch[x]] = r, fnd[rch[x]] = r;
    }

} lt;

这个在Find的时候进行路径压缩，在Pop之后的x所在的堆的原本的根指向其两个孩子合并后的新根。
_Merge的过程会重建被_Merge修改过的树的树状结构，但是_Merge总是只修改右侧的子树，所以路径压缩还是有点用的。

Init() 使用数组a初始化左偏树森林，每个元素单独是一个堆。
Merge(x,y) 合并第x个元素所属的左偏树和第y个元素所属的左偏树。若第x个元素或第y个元素已经被删除，直接返回。若第x个元素或第y个元素本身所属同一棵左偏树，直接返回。
Top(x) 返回第x个元素所属的左偏树的堆顶。若第x个元素已经被删除，返回-1。
Pop(x) 删除第x个元素所属的左偏树的堆顶。若第x个元素已经被删除，直接返回。

这里的堆顶，因为是if(val[x] > val[y] || val[x] == val[y] && x > y) swap(x, y); ，所以是小根堆，当多个元素的值都是最小值时，把序号小的放在堆顶。

要作为普通的堆使用时，给每个堆初始化放一个INF元素防止这个堆变成空堆就行（记得删除del相关的字段）。