代码：
/* code by: zstu wxk time: 2019/03/01 */ #include<bits/stdc++.h> using namespace std; #define Fopen freopen("testdata.in","r",stdin); freopen("_out.txt","w",stdout); #define LL long long #define ULL unsigned LL #define fi first #define se second #define pb push_back #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define lch(x) tr[x].son[0] #define rch(x) tr[x].son[1] #define max3(a,b,c) max(a,max(b,c)) #define min3(a,b,c) min(a,min(b,c)) typedef pair<int,int> pll; const int inf = 0x3f3f3f3f; const int _inf = 0xc0c0c0c0; const LL INF = 0x3f3f3f3f3f3f3f3f; const LL _INF = 0xc0c0c0c0c0c0c0c0; const LL mod = (int)1e9+7; const int N = 1e5 + 100; struct Node{ int son[2], rt; int val, pos, dis; Node(){ son[0] = son[1] = rt = 0; dis = 0; } }tr[N]; bool cmp(Node & t1, Node &t2){ if(t1.val == t2.val) return t1.pos < t2.pos; return t1.val < t2.val; } int n, m; int Find(int x){ if(x == tr[x].rt) return x; return tr[x].rt = Find(tr[x].rt); } int Merge(int u, int v){ if(u == v) return u; if(!u || !v) return u+v; if(!cmp(tr[u], tr[v])) swap(u, v); tr[u].son[1] = Merge(tr[u].son[1], v); tr[ tr[u].son[1] ].rt = u; if(tr[tr[u].son[0]].dis < tr[tr[u].son[1]].dis) swap(tr[u].son[1], tr[u].son[0]); tr[u].dis = tr[tr[u].son[1]].dis + 1; return u; } int Pop(int u){ if(!u || tr[u].pos == -1) return -1; tr[ tr[u].son[0] ].rt = tr[u].son[0]; tr[ tr[u].son[1] ].rt = tr[u].son[1]; tr[u].rt = Merge(tr[u].son[0], tr[u].son[1]); tr[u].pos = -1; return tr[u].val; } void Ac(){ tr[0].dis = -1; for(int i = 1; i <= n; ++i){ scanf("%d", &tr[i].val); tr[i].pos = i; tr[i].rt = i; } int op, u, v; for(int i = 1; i <= m; ++i){ scanf("%d", &op); if(op == 1){ scanf("%d%d", &u, &v); if(tr[u].pos == -1 || tr[v].pos == -1) continue; u = Find(u), v = Find(v); if(u == v) continue; Merge(u, v); } else { scanf("%d", &u); if(tr[u].pos == -1){ puts("-1"); continue; } printf("%d ", Pop(Find(u))); } } } int main(){ while(~scanf("%d%d", &n, &m)){ Ac(); } return 0; }