可并堆

可并堆，又叫左偏树，是一种支持合并的堆，以下内容基于小根堆（即根节点最小，大根堆类似），它支持以下功能：

1. 求一个数所在堆的根节点（复杂度同并查集路径压缩）
2. $O(1)$求最小值
3. $O(log\ n)$合并两个堆
4. $O(log\ n)$删除最小值
5. $O(log\ n)$插入一个数

$n$是堆的节点数。

维护信息

struct node{
    int l,r;//左右儿子
    int val;//权值
    int dep;//深度
    int fa;//父亲
}tr[N];

左偏表示$tr[ls].dep\ge tr[rs].dep$，这里的深度指的是从当前节点到其子树中最近的叶子节点的距离$+1$，由满二叉树的性质易知当$tr[rt].dep=k$时，该堆至少有$2^{k}-1$个节点

操作

求一个数所在堆的根

这里我们用并查集路径压缩的思想，可以保证时间复杂度。

int find(int u){
	if(tr[u].fa!=u) tr[u].fa=find(tr[u].fa);
	return tr[u].fa;
}

求最小值

找到一个数所在堆的根，直接访问根节点即可。

合并两个堆

#define ls tr[x].l
#define rs tr[x].r
int merge(int x,int y){
    if(!x||!y) return x+y;
    if(tr[x].val>tr[y].val||(tr[x].val==tr[y].val&&x>y)) swap(x,y);
    rs=merge(rs,y);//这样递归时rs的dep必然-1,可以保证时间复杂度为log级别,因为dep是log级别的
    if(tr[ls].dep<tr[rs].dep) swap(ls,rs);//保证左偏
    tr[x].dep=tr[rs].dep+1;
    return x;
}
int work(int x,int y){//合并x,y两个堆,返回根节点
    if(x==y) return 0;//同一个堆里就不用管了
    if(!x||!y) return tr[x+y].fa=x+y;//特殊情况
    tr[x].fa=tr[y].fa=merge(x,y);
    return x;
}

删除最小值

找到对应的根节点，合并其左右子树即可

void del(int x){
    tr[x].fa=work(ls,rs);
}

插入一个数

直接再开一个节点，然后合并两个堆即可

模板题

左偏树

#include<bits/stdc++.h>
#define x first
#define y second
#define endl '\n'
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define lowbit(x) ((x)&-(x))
#define SZ(x) (int)x.size()
using namespace std;
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using pdd=pair<ld,ld>;
const int INF=0x3f3f3f3f;
#define ls tr[x].l
#define rs tr[x].r
using namespace std;
const int N=1e5+10;
int n,m,w[N];
struct node{
    int l,r,val,dep,fa;//dep表示从当前节点到最近叶子节点的距离+1
}tr[N];
int find(int u){
	if(tr[u].fa!=u) tr[u].fa=find(tr[u].fa);
	return tr[u].fa;
}
int merge(int x,int y){
    if(!x||!y) return x+y;
    if(tr[x].val>tr[y].val||(tr[x].val==tr[y].val&&x>y)) swap(x,y);
    rs=merge(rs,y);
    if(tr[ls].dep<tr[rs].dep) swap(ls,rs);
    tr[x].dep=tr[rs].dep+1;
    return x;
}
int work(int x,int y){//合并x,y两个堆，返回根节点
    if(x==y) return 0;
    if(!x||!y) return tr[x+y].fa=x+y;
    tr[x].fa=tr[y].fa=merge(x,y);
    return x;
}
void del(int x){
    tr[x].fa=work(ls,rs);
}
bool vis[N];//记录每个数是否被删过
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>w[i],tr[i]={0,0,w[i],1,i};
	while(m--){
		int op,x,y;
		cin>>op>>x;
		if(op==1){
			cin>>y;
			if(vis[x]||vis[y]) continue;
			work(find(x),find(y));
		}
		else{
			if(vis[x]){
				cout<<-1<<endl;
				continue;
			}
			int tar=find(x);
			vis[tar]=1;
			cout<<tr[tar].val<<endl;
			del(tar);
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	solve();
	return 0;
}