<-----求赞$QAQ$

我觉得左偏树是最简单的数据结构之一了,但学了好像没啥用,因为都能被线段树合并切掉,但他短呀,居家懒人旅行必备

$0x00$ 一些概念和性质

空节点 : 没有左右儿子的结点称作空节点
点的距离$dist$ : 从点的子树到空节点的最短距离,空节点的$dist$为$-1$

以下左儿子称为$lc$,右儿子称为$rc$。

左偏树的性质:
$1.$ 具有堆性质
$2. dist_x = dist_{rc} + 1$
$3. n$个结点的左偏树深度为$\log_2 n$
$4. dist_{lc} \ge dist_{rc}$

$0x10$ 合并$merge$

左偏树的合并操作:合并两颗左偏树

首先将两个左偏树的根节点称为$x,y$

1. 如果$val_x > val_y$ 交换$x,y$
2. $rc$与$y$递归建树
3. 如果$dist_{lc} \le dist_{rc}$ 交换$lc, rc$
4. 更新$x$的$dist = dist_{rc} + 1$
5. 返回合并后的根节点$x$

左偏树的合并和$\text{FHQ_Treap}$很像,可以按它的理解方式来看

$Code:$

struct Node
{
    int v, id; //权值和插入时的编号
    int l, r, dist, root; //左儿子，右儿子，距离和根节点
    bool broken; //是否被删除
}tr[N];

int merge(int x, int y)
{
    if (!x || !y) return x | y; //返回非0根节点

    if (tr[x].v > tr[y].v || tr[x].v == tr[y].v && tr[x].id > tr[y].id) swap(x, y); // 1
    tr[x].r = merge(tr[x].r, y); //右子树和y下去递归 2

    if (tr[tr[x].l].dist < tr[tr[x].r].dist) swap(tr[x].l, tr[x].r); //3
    tr[x].dist = tr[tr[x].r].dist + 1; //更新距离,4

    return x; //5
}

例题 ： P3377 【模板】左偏树（可并堆）

需要支持以下操作
1. 合并$x,y$所在两个堆 若第 $x$ 或第 $y$ 个数已经被删除或第 $x$ 和第 $y$ 个数在用一个堆内，则无视此操作
2. 删除最小数，并输出

第一种操作:并查集维护根,左偏树合并
第二种操作:取出根节点,输出,然后合并左右子树

$Code:$

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

using namespace std;

const int N = 100010;

struct Node
{
    int v, id; //权值和插入时的编号
    int l, r, dist, root; //左儿子，右儿子，距离和根节点
    bool broken; //是否被删除
}tr[N];

int n, m;

int find(int x) //路径压缩
{
    if (tr[x].root != x) tr[x].root = find(tr[x].root);
    return tr[x].root;
}

int merge(int x, int y)
{
    if (!x || !y) return x | y; //返回非0根节点

    if (tr[x].v > tr[y].v || tr[x].v == tr[y].v && tr[x].id > tr[y].id) swap(x, y); //1
    tr[x].r = merge(tr[x].r, y); //右子树和y下去递归 2

    if (tr[tr[x].l].dist < tr[tr[x].r].dist) swap(tr[x].l, tr[x].r); // 3
    tr[x].dist = tr[tr[x].r].dist + 1; //更新距离 4

    return x; // 5
}

int main()
{
    scanf("%d%d", &n, &m);

    tr[0].dist = -1; //0号点dist为-1
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &tr[i].v);
        tr[i].id = i;
        tr[i].root = i; //并查集
    }

    while (m -- )
    {
        int op, x, y;
        scanf("%d", &op);

        if (op == 1) 
        {
            scanf("%d%d", &x, &y);

            if (tr[x].broken | tr[y].broken) continue; //被删了

            x = find(x), y = find(y);
            if (x != y) tr[x].root = tr[y].root = merge(x, y); //合并
        }
        else
        {
            scanf("%d", &x);
            if (tr[x].broken) 
            {
                puts("-1");
                continue;
            }

            x = find(x);
            printf("%d\n", tr[x].v);
            tr[x].broken = true;
            tr[tr[x].l].root = tr[tr[x].r].root = tr[x].root = merge(tr[x].l, tr[x].r);
            //tr[x].root赋值是因为有些点的根仍指向x,在路径压缩时会炸
            tr[x].l = tr[x].r = tr[x].dist = 0; //删除x
        }
    }

    return 0;
}