[luoguP3377] 左偏树/可并堆

题意

原题链接
给定 \(n\) 个小根堆，初始只有一个元素 \(a_i\)，给出 \(m\) 次操作，每次合并堆 \(x,y\) 所在的两个堆或删除 \(x\) 所在的堆顶并输出堆顶

sol

由于堆需要合并，因此需要实现一种合并时间复杂度为 \(O(\log n)\) 的堆数据结构（本题也可 \(O(m\log^2 n)\) 启发式合并），其中一种是左偏树。
左偏树，即向左偏的树，它每个节点的左儿子到最近的外节点的距离一定不小于右儿子到最近的外节点的距离（我们把少于两个儿子的节点叫做外节点），容易得到，根节点到最近的外节点的距离等于右儿子到最近的外节点的距离加一。
在合并时，将权值更小的点作为根，将它的右儿子和另一个堆递归合并，合并后若不满足左偏树性质，则交换左右儿子。
插入节点时，只需要将一个节点的堆与其合并即可；删除根节点时，只需要合并左右儿子即可。
注意本题需要并查集来维护所在的堆。

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100005;

struct Node{
    int val;
    int l = 0, r = 0;
    int dist = 0;
}tr[N];

bool st[N];
int fa[N];
int n, m;

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

int merge(int x, int y){
    if (!x || !y) return x | y;
    if (tr[x].val > tr[y].val) swap(x, y);
    tr[x].r = merge(tr[x].r, y);
    if (tr[tr[x].l].dist < tr[tr[x].r].dist) swap(tr[x].l, tr[x].r);
    tr[x].dist = tr[tr[x].r].dist + 1;
    return x;
}

int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &tr[i].val), fa[i] = i;
    while (m -- ){
        int op;
        scanf("%d", &op);
        if (op == 1){
            int x, y;
            scanf("%d%d", &x, &y);
            int fx = find(x), fy = find(y);
            if (fx == fy || st[x] || st[y]) continue;
            fa[fx] = fa[fy] = merge(fx, fy);
        }
        else {
            int x;
            scanf("%d", &x);
            int fx = find(x);
            if (st[x]) puts("-1");
            else {
                printf("%d\n", tr[fx].val);
                st[fx] = true;
                fa[fx] = fa[tr[fx].l] = fa[tr[fx].r] = merge(tr[fx].l, tr[fx].r);
                tr[fx].l = tr[fx].r = tr[fx].dist = 0;
            }
        }
    }
}