提交记录

代码：

#include<bits/stdc++.h>
namespace Limie{
	#define x first
	#define y second
	using namespace std;
	typedef long long LL;
	typedef pair<int,int> PII;
	typedef unsigned long long ULL;
	typedef long double LD;
}
using namespace Limie;
int n,m;
struct Node{
	int w,fa;
	vector<int> son;
}tr[100010]; 
int p[100010];
int h[100010],l[100010],r[100010],mn[100010];
int d[100010];
bool st[100010];
int find(int x)
{
	if(p[x]!=x)p[x]=find(p[x]);
	return p[x];
}
int merge(int x,int y)
{
	if(tr[x].w>tr[y].w||tr[x].w==tr[y].w&&x>y)x^=y^=x^=y;
	tr[x].son.push_back(y);
	tr[y].fa=x;
	return x; 
}
void rebuild(int x)
{
	int y=h[x];
	mn[x]=y;
	do{
		while(d[tr[y].son.size()]){
			int t=d[tr[y].son.size()];
			if(h[x]==t)h[x]=r[t];
			r[l[t]]=r[t],l[r[t]]=l[t];
			d[tr[y].son.size()]=0;
			int a=l[y],b=r[y];
			int la=y;
			y=merge(y,t);
			if(h[x]==la)h[x]=y;
			r[a]=y,l[y]=a,r[y]=b,l[b]=y;
		}
		d[tr[y].son.size()]=y;
		if(tr[mn[x]].w>tr[y].w||tr[mn[x]].w==tr[y].w&&mn[x]>y)mn[x]=y;
		y=r[y];
	}while(y!=h[x]);
	y=h[x];
	do{d[tr[y].son.size()]=0;}while(y!=h[x]);
}
int main()
{
	int i;
	cin>>n>>m;
	for(i=1;i<=n;i++){
		int x;
		cin>>x;
		tr[i].w=x,tr[i].fa=p[i]=mn[i]=h[i]=l[i]=r[i]=i;
	}
	while(m--){
		int x,y,ty;
		cin>>ty>>x;
		if(ty==1){
			cin>>y;
			if(st[x]||st[y])continue;
			x=find(x),y=find(y);
			if(x==y)continue;
			p[y]=x;
			if(tr[mn[x]].w>tr[mn[y]].w||tr[mn[x]].w==tr[mn[y]].w&&mn[x]>mn[y])
			mn[x]=mn[y];
			x=h[x],y=h[y];
			r[l[y]]=r[x],l[r[x]]=l[y];
			r[x]=y,l[y]=x;
		}
		else{
			if(st[x]){
				puts("-1");
				continue;
			}
			int rt=find(x);
			x=mn[rt];
			cout<<tr[x].w<<'\n';
			st[x]=1;
			if(h[rt]==x){
				if(r[x]==x){
					h[rt]=0;
					continue;
				}
				h[rt]=r[x];
			}
			int la=l[x];
			for(int y:tr[x].son)tr[y].fa=y,r[la]=y,l[y]=la,la=y;
			r[la]=r[x],l[r[x]]=la;
			rebuild(rt);
		}
	}
}