可并堆模板

#include<string.h>
#include<stdlib.h>
#include<stdio.h>
//#include<assert.h>
#include<algorithm>
//#include<iostream>
using namespace std;

int n,m;
#define maxn 200011
int root[maxn]; bool die[maxn];
int find(int x) {return root[x]==x?x:(root[x]=find(root[x]));}
struct leftist
{
    int v[maxn],id[maxn],dis[maxn],ls[maxn],rs[maxn],size;
    leftist() {size=0; dis[0]=-1;}
    int merge(int x,int y)
    {
        if (!x || !y) return x^y;
        if (v[x]>v[y] || (v[x]==v[y] && id[x]>id[y])) {int t=x;x=y;y=t;}
        rs[x]=merge(rs[x],y);
        if (dis[ls[x]]<dis[rs[x]]) {int t=ls[x]; ls[x]=rs[x]; rs[x]=t;}
        dis[x]=dis[rs[x]]+1;
        return x;
    }
    void push(int &root,int val,int Id)
    {
        int x=++size; v[x]=val; id[x]=Id; dis[x]=0; ls[x]=rs[x]=0;
        root=merge(root,x);
    }
    int top(int &root) {return v[root];}
    void pop(int &root) {root=merge(ls[root],rs[root]);}
}q;

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1,x;i<=n;i++) scanf("%d",&x),q.push(root[i],x,i);
    int x,y,op;
    while (m--)
    {
        scanf("%d",&op);
        if (op==2)
        {
            scanf("%d",&x);
            if (die[x]) puts("-1");
            else
            {
                x=find(x);
                printf("%d
",q.top(x));
                die[x]=1;
                q.pop(root[x]); root[root[x]]=root[x];
            }
        }
        else
        {
            scanf("%d%d",&x,&y);
            if (die[x] || die[y]) continue;
            x=find(x),y=find(y); if (x==y) continue;
            root[x]=root[y]=q.merge(root[x],root[y]);
        }
    }
    return 0;
}