首页 > 代码库 > 左偏树

左偏树

真不好意思把luogu的链接放出来,数据也太水了把,想吐。。

简单叙述一下题意把,不粘贴了,没有脸。

刚开始给定若干个堆,然后你可以吧两个堆合并,或者删除值为x并输出x所在的堆min

%:pragma GCC optimize("O3")#include<bits/stdc++.h>#define maxn 200000using namespace std;struct TREE{int val,dis,l,r;}tr[maxn];int x,y,t1,n,m,fa[maxn];template<typename tp>void read(tp & dig){    char c=getchar();dig=0;    while(!isdigit(c))c=getchar();    while(isdigit(c))dig=dig*10+c-‘0‘,c=getchar();}inline int find(int x){while(fa[x]) x=fa[x];return x;}//这里不是并查集,而是找他的父节点 inline int merge(int a,int b){	if(!a) return b;if(!b) return a;	if(tr[a].val>tr[b].val||(tr[a].val==tr[b].val&&a>b)) swap(a,b);//维护一个小根堆 	tr[a].r=merge(tr[a].r,b);	fa[tr[a].r]=a;	if(tr[tr[a].l].dis<tr[tr[a].r].dis) swap(tr[a].l,tr[a].r);	if(tr[a].r==0) tr[a].dis=0;	else tr[a].dis=tr[tr[a].r].dis+1;	return a;}int main(){	read(n),read(m);tr[0].val=-1;//这里要加上,luogu数据真心水 	for(int i=1;i<=n;i++)read(tr[i].val);	while(m--)	{		read(t1);		if(t1==1)		{			read(x),read(y);			if(tr[x].val==-1||tr[y].val==-1) continue;			x=find(x),y=find(y);			if(x!=y) merge(x,y);		}		if(t1==2)		{			read(x);			if(tr[x].val==-1) puts("-1");			else 			{				printf("%d\n",tr[x=find(x)].val);				fa[tr[x].l]=fa[tr[x].r]=0;				merge(tr[x].l,tr[x].r);				tr[x].val=-1; 			}		}	}	return 0;}

 

左偏树