左偏树代码如下

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int n,m;
struct node{
	int val,fa,lc,rc,dis;
	bool del;
	friend bool operator <(node u,node v)
	{
		return u.val==v.val?u<v:u.val<v.val;
	}
}lf[MAXN];
#define rs(u) lf[u].rc
#define ls(u) lf[u].lc
#define d(u) lf[u].del
int find(int u){return lf[u].fa==u?u:lf[u].fa=find(lf[u].fa);}
int merge(int u,int v)
{
	if(!u||!v) return u+v;
	if(lf[v]<lf[u]) swap(u,v);
	lf[u].rc=merge(lf[u].rc,v);
	if(lf[ls(u)].dis<lf[rs(u)].dis) swap(ls(u),rs(u));
	lf[u].dis=lf[rs(u)].dis+1;
	return u;
}
signed main()
{
	lf[0].dis=-1;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&lf[i].val),lf[i].fa=i,lf[i].del=0;
	while(m--)
	{
		int op,x;
		scanf("%d%d",&op,&x);
		if(op==1)
		{
			int y;
			scanf("%d",&y);
			if(d(x)||d(y)) continue;
			int a=find(x);
			int b=find(y);
			if(a==b) continue;
			lf[a].fa=lf[b].fa=merge(a,b);
		}
		if(op==2)
		{
			if(d(x))
			{
				puts("-1");
				continue;
			}
			int nw=find(x);
			printf("%d\n",lf[nw].val);
			d(nw)=1;
			lf[ls(nw)].fa=lf[rs(nw)].fa=lf[nw].fa/*路径压缩导致可能会指向老根*/=merge(ls(nw),rs(nw));
			ls(nw)=rs(nw)=lf[nw].dis=0;
		}
	}
	return 0;
}

MLE记录

TLE记录