左偏树（Leftist-tree） Luogu P3377 模板

左偏树(Leftist-tree)

性质

• 节点的键值小于或等于左右子节点的键值。这是左偏树的堆性质。
• 节点的左子节点的距离不小于右子节点的距离。
• 节点的距离等于它的右子节点距离加一。

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define N 200001
using namespace std;
const int INF = 0x3f3f3f3f;
struct node{
	int val,lc,rc,dis,fa;
}tree[N];
int tot,n,m;
int init(){
	for(int i = 1;i <= n;++i){
		tree[i].lc = tree[i].rc = tree[i].dis = 0;
		tree[i].fa = i;
	}
}
int merge(int x,int y){
	if(x == 0) return y;
	if(y == 0) return x;
	if(tree[x].val > tree[y].val || (tree[x].val == tree[y].val && x > y) )
		swap(x,y);
	tree[x].rc = merge(tree[x].rc,y);
	tree[tree[x].rc].fa = x;
	if(tree[tree[x].rc].dis > tree[tree[x].lc].dis)
		swap(tree[x].rc,tree[x].lc);
	tree[x].dis = tree[x].rc == 0 ? 0 : tree[tree[x].rc].dis + 1;
}
int findset(int x){
	while(tree[x].fa != x){
		x = tree[x].fa;
	}
	return x;
}
int add(int val,int x){
	tree[tot].lc = tree[tot].rc = tree[tot].dis = 0;
	tree[tot++].val = val;
	return merge(tot - 1,x);	
}
int del(int x){
	int l = tree[x].lc,r = tree[x].rc;
	tree[x].fa = tree[x].lc = tree[x].rc = tree[x].dis = 0;
	tree[x].val = -INF;
	tree[l].fa = l;
	tree[r].fa = r;
	return merge(l,r);
}
int build()
{
	queue<int> Q;
	for(int i = 1;i <= n;++i)
		Q.push(i);
	while(!Q.empty()){
		if(Q.size() == 1) break;
		else{
			int x = Q.front();Q.pop();
			int y = Q.front();Q.pop();
			Q.push(merge(x,y));
		}
	}
	int final = Q.front();Q.pop();
	return final;
}
int main()
{
	scanf("%d%d",&n,&m);
	init();
	for(int i = 1;i <= n;++i){
		scanf("%d",&tree[i].val);
	}
	int op,a,b;
	for(int i = 1;i <= m;++i){
		scanf("%d",&op);
		if(op == 1){
			scanf("%d%d",&a,&b);
			int fx = findset(a),fy = findset(b);
			if(tree[a].val == INF || tree[b].val == INF || fx == fy){
				continue;
			} else {
				merge(fx,fy);
			}
		} else {
			scanf("%d",&a);
			if(tree[a].val == -INF){
				printf("-1
");
			} else {
				int tmp = findset(a);
				printf("%d
",tree[tmp].val);
				del(tmp);
			}
		}
	}
	return 0;
}