ref(orz Melacau):
https://www.cnblogs.com/Melacau/p/leftist_tree.html
Code(luogu 3377):
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define MN 100005 5 using namespace std; 6 inline int in(){ 7 int x=0;bool f=0; char c; 8 for (;(c=getchar())<'0'||c>'9';f=c=='-'); 9 for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0'); 10 return f?-x:x; 11 } 12 int ch[2][MN],a[MN],d[MN],fa[MN]; 13 int n,m,tp,x,y,fx,fy; 14 inline int gf(int x){return fa[x]?gf(fa[x]):x;} 15 inline int merge(int x,int y){ 16 if (!x) return y;if (!y) return x; 17 if (a[x]>a[y]||(a[x]==a[y]&&x>y)) swap(x,y); 18 ch[1][x]=merge(ch[1][x],y);fa[ch[1][x]]=x; 19 if (d[ch[0][x]]<d[ch[1][x]]) swap(ch[0][x],ch[1][x]); 20 d[x]=d[ch[1][x]]+1;return x; 21 } 22 inline void pop(int x){ 23 a[x]=-1;fa[ch[0][x]]=fa[ch[1][x]]=0; 24 merge(ch[0][x],ch[1][x]); 25 } 26 int main() 27 { 28 n=in();m=in();d[0]=-1; 29 for (int i=1;i<=n;++i) a[i]=in(); 30 for (int i=1;i<=m;++i){ 31 tp=in();x=in(); 32 if (tp==1){ 33 y=in();if (a[x]==-1||a[y]==-1) continue; 34 if (x==y) continue; 35 fx=gf(x);fy=gf(y);merge(fx,fy); 36 }else { 37 if (a[x]==-1) puts("-1"); 38 else fx=gf(x),printf("%d ",a[fx]),pop(fx); 39 } 40 }return 0; 41 }