【题目来源】
【题目描述】
你需要维护一个小根堆的集合，初始时集合是空的。
该集合需要支持如下四种操作：
● 1 a，在集合中插入一个新堆，堆中只包含一个数 a。
● 2 x y，将第 x 个插入的数和第 y 个插入的数所在的小根堆合并。数据保证两个数均未被删除。若两数已在同一堆中，则忽略此操作。
● 3 x，输出第 x 个插入的数所在小根堆的最小值。数据保证该数未被删除。
● 4 x，删除第 x 个插入的数所在小根堆的最小值（若最小值不唯一，则优先删除先插入的数）。数据保证该数未被删除。
【输入格式】
第一行包含整数 n，表示总操作数量。
接下来 n 行，每行包含一个操作命令，形式如题所述。
【输出格式】
对于每个操作 3，输出一个整数，占一行，表示答案。
【输入样例】
6
1 3
1 2
2 1 2
3 1
4 2
3 1
【输出样例】
2
3
【数据范围】
1≤n≤2×10^5，
1≤a≤10^9，
1≤x,y≤当前插入数的个数。
数据保证所有操作合法。
【算法分析】
● 左偏树
（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=2e5+5;
int v[N],dist[N],le[N],ri[N],idx;
int pre[N];
int n;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 mergingif(!x || !y) return x+y;if(cmp(y,x)) 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 main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);v[0]=INT_MAX;cin>>n;while(n--) {int op,x,y;cin>>op>>x;if(op==1) {v[++idx]=x;dist[idx]=0;pre[idx]=idx;} else if(op==2) {cin>>y;x=find(x),y=find(y);if(x!=y) {if(cmp(y,x)) swap(x,y);pre[y]=x;merge(x,y);}} else if(op==3) cout<<v[find(x)]<<"\n";else {x=find(x);if(cmp(ri[x],le[x])) swap(ri[x],le[x]);pre[x]=le[x],pre[le[x]]=le[x];merge(le[x],ri[x]);}}return 0;
}/*
in:
6
1 3
1 2
2 1 2
3 1
4 2
3 1out:
2
3
*/
【参考文献】