【模板】左偏树（可并堆）

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
const int maxx = 2e5+6;
struct node{
   int rt,l,r,val,pos,dis;
   node(){
     l=r=val=dis=pos=0;
   }
}tree[maxx];
int n,m;
bool cmp(node a,node b){
    if (a.val==b.val)return a.pos<b.pos;
    return a.val<b.val;
}
int Find(int x){
   if (x==tree[x].rt)return x;
   return tree[x].rt=Find(tree[x].rt);
}
int Merge(int u,int v)
{
    if(u==v)return u;
    ///如果有一个节点为空
    if(!u || !v)return u+v;
    ///如果满足性质二叉堆的性质
    if(!cmp(tree[u],tree[v]))swap(u,v);
    ///继续向右合并
    tree[u].r=Merge(tree[u].r,v);
    ///向上合并
    tree[tree[u].r].rt=u;
    if(tree[tree[u].l].dis<tree[tree[v].r].dis)swap(tree[u].r,tree[u].l);
    tree[u].dis=tree[tree[u].l].dis+1;
    return u;
}
int pop(int u)
{
    if(!u || tree[u].pos==-1)return -1;
    tree[tree[u].l].rt=tree[u].l;
    tree[tree[u].r].rt=tree[u].r;
    tree[u].rt=Merge(tree[u].l,tree[u].r);
    tree[u].pos=-1;
    return tree[u].val;
}
void ac(){
  tree[0].dis=-1;
  for (int i=1;i<=n;i++){
      scanf("%d",&tree[i].val);
      tree[i].pos=i;
      tree[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(tree[u].pos==-1 || tree[v].pos==-1)continue;
        u=Find(u),v=Find(v);
        if (v==u)continue;
        Merge(u,v);
    }else{
       scanf("%d",&u);
       if (tree[u].pos==-1){
        printf("-1
");
        continue;
       }
       printf("%d
",pop(Find(u)));
    }
  }
}
int main(){
  scanf("%d%d",&n,&m);
  ac();
  return 0;
}