题目描述
如题，一开始有N个小根堆，每个堆包含且仅包含一个数。接下来需要支持两种操作：

操作1： 1 x y 将第x个数和第y个数所在的小根堆合并（若第x或第y个数已经被删除或第x和第y个数在用一个堆内，则无视此操作）

操作2： 2 x 输出第x个数所在的堆最小数，并将其删除（若第x个数已经被删除，则输出-1并无视删除操作）

输入格式
第一行包含两个正整数N、M，分别表示一开始小根堆的个数和接下来操作的个数。

第二行包含N个正整数，其中第i个正整数表示第i个小根堆初始时包含且仅包含的数。

接下来M行每行2个或3个正整数，表示一条操作，格式如下：

操作1 ： 1 x y

操作2 ： 2 x

输出格式
输出包含若干行整数，分别依次对应每一个操作2所得的结果。

输入输出样例
输入 #1复制
5 5
1 5 4 2 3
1 1 5
1 2 5
2 2
1 4 2
2 2
输出 #1复制
1
2

就是一些堆的合并，于是我们可以用到左偏树。

写法和无旋treap差不多。

然后并查集表示当前块的位置，找到对应的堆的顶点。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int ch[N][2],val[N],dis[N],f[N],n,m;
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
int merge(int x,int y){
	if(!x||!y)	return x+y;
	if(val[x]>val[y]||val[x]==val[y]&&x>y)	swap(x,y);
	ch[x][1]=merge(ch[x][1],y); f[ch[x][1]]=x;
	if(dis[ch[x][0]]<dis[ch[x][1]])	swap(ch[x][0],ch[x][1]);
	dis[x]=dis[ch[x][1]]+1;
	return x;
}
inline void pop(int x){
	val[x]=-1; f[ch[x][0]]=ch[x][0]; f[ch[x][1]]=ch[x][1];
	f[x]=merge(ch[x][0],ch[x][1]);
}
signed main(){
	cin>>n>>m; dis[0]=-1;
	for(int i=1;i<=n;i++)	scanf("%d",&val[i]),f[i]=i;
	while(m--){
		int op;	scanf("%d",&op);
		if(op==1){
			int x,y;	scanf("%d %d",&x,&y);
			if(val[x]==-1||val[y]==-1||x==y)	continue;
			int fa=find(x),fb=find(y);
			merge(fa,fb);	
		}else{
			int x;	scanf("%d",&x);
			if(val[x]==-1)	puts("-1");
			else{
				int fa=find(x); printf("%d\n",val[fa]); pop(fa);
			}
		}
	}
	return 0;
}