洛谷 P3377：[模板] 可并堆 1 ← 左偏树

​【题目来源】
https://www.luogu.com.cn/problem/P3377

【题目描述】
如题，一开始有 n 个小根堆，每个堆包含且仅包含一个数。
接下来需要支持两种操作：
1. 1 x y：将第 x 个数和第 y 个数所在的小根堆合并（若第 x 或第 y 个数已经被删除或第 x 和第 y 个数在同一个堆内，则无视此操作）。
2. 2 x：输出第 x 个数所在的堆最小数，并将这个最小数删除（若有多个最小数，优先删除先输入的；若第 x 个数已经被删除，则输出 -1 并无视删除操作）。

【输入格式】
第一行包含两个正整数 n，m，分别表示一开始小根堆的个数和接下来操作的个数。
第二行包含 n 个正整数，其中第 i 个正整数表示第 i 个小根堆初始时包含且仅包含的数。
接下来 m 行每行 2 个或 3 个正整数，表示一条操作，格式如下：
操作 1：1 x y
操作 2：2 x

【输出格式】
输出包含若干行整数，分别依次对应每一个操作 2 所得的结果。

【输入样例】
5 5
1 5 4 2 3
1 1 5
1 2 5
2 2
1 4 2
2 2

【输出样例】
1
2

【数据范围】
对于 30% 的数据：n≤10，m≤10。
对于 70% 的数据：n≤10^3，m≤10^3。
对于 100% 的数据：n≤10^5，m≤10^5，初始时小根堆中的所有数都在 int 范围内。

【算法分析】
● 左偏树
（1）左偏树是一种可合并的堆（也叫 “可并堆”），它在普通二叉堆（大根 / 小根堆）的基础上，增加了「快速合并两个堆」的能力，同时保证堆的性质（小根堆：父节点≤子节点；大根堆反之）。普通二叉堆合并两个堆的时间复杂度是 O(n)，而左偏树能做到 O(logn)，这是它的核心优势。
（2）STL 未提供左偏树的实现，必须手动实现（指针 / 结构体 + 递归）。

● 左偏树的距离
左偏树的距离（dist）是其核心定义，用于保证左偏性质与合并效率。
一、先定义 “外节点”（External Node）
外节点：左子树为空或右子树为空的节点（叶子节点一定是外节点）。

二、节点距离 dist (x) 的定义
对任意节点 x：
若 x 是外节点：dist(x) = 0
若 x 不是外节点：dist (x) = 从 x 到其后代中最近的外节点所经过的边数
空节点（NULL）：dist(NULL) = -1（约定）
三、左偏树的距离（整棵树的距离）
整棵左偏树的距离 = 根节点的 dist 值。
四、关键性质（由左偏性导出）
左偏树满足：对任意节点 x，dist (left (x)) ≥ dist (right (x))。
由此可推出：dist(x) = dist(right(x)) + 1
也就是说：节点的距离等于其右子树的距离 + 1。
这是左偏树合并、维护时最常用的公式。

【算法代码】

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

const int N=1e5+5;
int v[N],dist[N],le[N],ri[N];
int pre[N];
int n,m;

bool cmp(int x,int y) {
    if(v[x]!=v[y]) return v[x]<v[y];
    return x<y;
}

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

int merge(int x,int y) { //Return the root node after merging
    if(!x || !y) return x+y;
    if (!cmp(x,y)) swap(x,y);
    ri[x]=merge(ri[x],y);
    if(dist[le[x]]<dist[ri[x]]) swap(le[x],ri[x]);
    dist[x]=dist[ri[x]]+1;
    return x;
}

int get_root(int x) {
    if(!dist[x]) return 0;
    int fx=find(x);
    return dist[fx]==0?0:fx;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        cin>>v[i];
        pre[i]=i;
        dist[i]=1; //not 0
    }

    while(m--) {
        int op,x,y;
        cin>>op>>x;
        if(op==1) {
            cin>>y;
            int fx=get_root(x),fy=get_root(y);
            if(fx && fy && fx!=fy) {
                int root=merge(fx,fy);
                pre[fx]=pre[fy]=root;
            }
        } else {
            if(!dist[x]) {
                cout<<-1<<"\n";
                continue;
            }
            int rt=find(x);
            cout<<v[rt]<<"\n";
            dist[rt]=0;
            pre[rt]=merge(le[rt],ri[rt]);
            if(pre[rt]) pre[pre[rt]]=pre[rt];
        }
    }

    return 0;
}

/*
in:
5 5
1 5 4 2 3
1 1 5
1 2 5
2 2
1 4 2
2 2

out:
1
2
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/158237475
https://oi-wiki.org/ds/leftist-tree/
https://chuna2.787528.xyz/zdsrs060330/p/16095189.html
https://blog.csdn.net/hnjzsyjyj/article/details/158207666
https://www.acwing.com/solution/content/161640/
https://chuna2.787528.xyz/qkhm/p/LeftTree.html
https://blog.csdn.net/qq_46105170/article/details/126205297



 

​