【模板】左偏树 / 可并堆

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
int h[100005];
priority_queue<PII,vector<PII>,greater<PII> > q[100005];
int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		q[i].push(make_pair(x,i));
		h[i]=i;
	}
	while(m--)
	{
		int op,x,y;
		scanf("%d %d",&op,&x);
		if(op==1)
		{
			scanf("%d",&y);
			int hx=h[x],hy=h[y];
			if(hx==hy||!hx||!hy)continue;
			if(q[hx].size()>q[hy].size())swap(hx,hy);
			while(!q[hx].empty())
			{
				PII t=q[hx].top();
				q[hx].pop();
				q[hy].push(t);
				h[t.second]=hy;
			}
		}
		else
		{
			int hx=h[x];
			if(!hx)puts("-1");
			else
			{
				PII t=q[hx].top();
				printf("%d\n",t.first);
				q[hx].pop();
				h[t.second]=0;
			}
		}
	}
	return 0;
}