题目链接
2714. 左偏树
你需要维护一个小根堆的集合，初始时集合是空的。
该集合需要支持如下四种操作：
1 a，在集合中插入一个新堆，堆中只包含一个数 \(a\)。2 x y，将第 \(x\) 个插入的数和第 \(y\) 个插入的数所在的小根堆合并。数据保证两个数均未被删除。若两数已在同一堆中，则忽略此操作。3 x，输出第 \(x\) 个插入的数所在小根堆的最小值。数据保证该数未被删除。4 x，删除第 \(x\) 个插入的数所在小根堆的最小值（若最小值不唯一，则优先删除先插入的数）。数据保证该数未被删除。
输入格式
第一行包含整数 \(n\)，表示总操作数量。
接下来 \(n\) 行，每行包含一个操作命令，形式如题所述。
输出格式
对于每个操作 \(3\)，输出一个整数，占一行，表示答案。
数据范围
\(1 \le n \le 2 \times 10^5\),
\(1 \le a \le 10^9\),
\(1 \le x,y \le\) 当前插入数的个数。
数据保证所有操作合法。
输入样例：
6
1 3
1 2
2 1 2
3 1
4 2
3 1
输出样例：
2
3
解题思路
左偏树
左偏树作为可并堆的一种数据结构，其重点在于将两个堆合并，在维护堆的性质之外，每个节点 \(x\) 另外维护一个信息 \(dist[x]\) 表示 \(x\) 到最近的叶子节点的距离，且要求所有的左子树 \(l\) 和右子树 \(r\) 都有这样的关系：\(dist[l]\geq dist[r]\)，这样可以保证合并的复杂度为 \(O(logn)\)，具体证明不再赘述。以小根堆为例，合并 \(x,y\) 时 即将大的最为小的一棵子树，即递归合并，如果发现有不满足左偏树 \(dist\) 性质的情况，交换左右两棵子树即可
本题另外需要用并查集维护集合关系
- 时间复杂度：\(O(nlogn)\)
代码
// Problem: 左偏树
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2716/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
// %%%Skyqwq
#include <bits/stdc++.h>
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template <typename T> void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N=2e5+5;
int n,op,x,y,cnt;
int fa[N],v[N],l[N],r[N],dist[N];
bool cmp(int x,int y)
{
if(v[x]!=v[y])return v[x]<v[y];
return x<y;
}
int find(int x)
{
return x==fa[x]?x:fa[x]=find(fa[x]);
}
int merge(int x,int y)
{
if(!x||!y)return x+y;
if(cmp(y,x))swap(x,y);
r[x]=merge(r[x],y);
if(dist[l[x]]<dist[r[x]])swap(l[x],r[x]);
dist[x]=dist[r[x]]+1;
return x;
}
void pop(int x)
{
int y=merge(l[x],r[x]);
fa[x]=y,fa[y]=y;
}
int main()
{
for(cin>>n;n;n--)
{
cin>>op>>x;
if(op==1)
{
v[++cnt]=x;
dist[cnt]=1;
fa[cnt]=cnt;
}
else if(op==2)
{
cin>>y;
x=find(x),y=find(y);
if(x!=y)
{
if(cmp(y,x))swap(x,y);
fa[y]=x;
merge(x,y);
}
}
else if(op==3)printf("%d\n",v[find(x)]);
else
pop(find(x));
}
return 0;
}