云剪贴板 pahh68fy

# 板子 ```cpp #include<bits/stdc++.h> #define dist(p) tr[p].dist #define val(p) tr[p].val #define l(p) tr[p].l #define r(p) tr[p].r #define fa(p) tr[p].fa using namespace std; const int N=2e5+10; struct tree{ int val,l,r,fa,dist; }tr[N]; int n,m; inline int find(int x){return fa(x)==x?x:fa(x)=find(fa(x));} inline int merge(int x,int y) { if(!x|!y)return x|y; if(val(x)>val(y))swap(x,y); r(x)=merge(r(x),y); if(dist(l(x))<dist(r(x)))swap(l(x),r(x)); dist(x)=dist(r(x))+1; fa(l(x))=fa(r(x))=fa(x)=x; return x; } inline void pop(int x) { val(x)=-1; fa(l(x))=l(x); fa(r(x))=r(x); fa(x)=merge(l(x),r(x)); } int main() { scanf("%d %d",&n,&m); for(int i=1;i<=n;++i)scanf("%d",&val(i)),fa(i)=i; for(int i=1,t,x,y;i<=m;++i) { scanf("%d %d",&t,&x); if(t==1) { scanf("%d",&y); if(val(x)==-1||val(y)==-1)continue; int l=find(x),r=find(y); if(l!=r)fa(l)=fa(r)=merge(l,r); } else { if(val(x)==-1)puts("-1"); else printf("%d\n",val(find(x))),pop(find(x)); } } return 0; } ```