【题目来源】
【题目描述】
如题，一开始有 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 mergingif(!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 2out:
1
2
*/
【参考文献】