## 正文

### 算法函数

int merge(int x,int y/*要进行合并的两棵树的根*/) {
if (!x or !y) {
return x+y;
}
if (val[x]>val[y] or (val[x]==val[y] and x>y)/*可以根据大小跟堆调整大小余号*/) {
swap(x,y);//维护左偏
}
r[x]=merge(r[x],y);//递归寻找右子树
fa[l[x]]=fa[r[x]]=fa[x]=x;
if (dis[l[x]]<dis[r[x]]) {
swap(l[x],r[x]);//依旧维护
}
dis[x]=dis[r[x]]+1;//更新根节点到叶子节点的最短路径
return x;
}


if (!x or !y) {
return x+y;
}


//删除堆顶
void Delete(int x) {
vis[x]=1;
fa[l[x]]=l[x],fa[r[x]]=r[x];
fa[x]=merge(l[x],r[x]);
}
//任意
void Delete(int x) {
int L=l[x],R=r[x];
fa[L]=L,fa[R]=R;
l[x]=r[x]=dis[x]=0;
merge(merge(L,R),find(x));
}



#include <iostream>

using namespace std;
int n,m;
int val[1000001],fa[1000001];
int dis[1000001],vis[1000001];
int r[1000001],l[1000001];

int find (int x) {return (fa[x]==x?x:fa[x]=find(fa[x]));}

int merge(int x,int y) {
if (!x or !y) {
return x+y;
}
if (val[x]>val[y] or (val[x]==val[y] and x>y)) {
swap(x,y);
}
r[x]=merge(r[x],y);
fa[l[x]]=fa[r[x]]=fa[x]=x;
if (dis[l[x]]<dis[r[x]]) {
swap(l[x],r[x]);
}
dis[x]=dis[r[x]]+1;
return x;
}

void join(int x,int y) {
int nx=find(x),ny=find(y);
if (vis[x] or vis[y] or nx==ny) {
return;
}
fa[nx]=fa[ny]=merge(nx,ny);
}

void Delete(int x) {
vis[x]=1;
fa[l[x]]=l[x],fa[r[x]]=r[x];
fa[x]=merge(l[x],r[x]);
}

int get_ans(int x) {
if (vis[x]) {
return 0;
}
int nx=find(x);
Delete(nx);
return val[nx];
}

int main() {
cin>>n;
for (int i=1;i<=n;i++) {
cin>>val[i];
fa[i]=i;
}
cin>>m;
for (int i=1,x,y;i<=m;i++) {
int tmp;
cin>>tmp>>x;
if (tmp==1) {
cin>>y;
join(x,y);
} else if (tmp==2){
cout<<get_ans(x)<<endl;
}
}
return 0;
}


p2713

p4971

p1456