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

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC optimize("Ofast,no-stack-protector")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

//#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define pi acos(-1.0)

#define ll long long

#define vi vector<int>

#define mod 1000000007

#define C 0.5772156649

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#define pil pair<int,ll>

#define pli pair<ll,int>

#define pii pair<int,int>

#define cd complex<double>

#define ull unsigned long long

#define base 1000000000000000000

#define fio ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

const double g=10.0,eps=1e-12;

const int N=100000+10,maxn=1000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;

int val[N],dis[N],f[N],ch[N][2];

int Merge(int x,int y)

{

    if(x==0||y==0)return x+y;

    if(val[x] > val[y] ||val[x]==val[y] && x>y)swap(x,y);

    ch[x][1] = Merge(ch[x][1],y);

    f[ch[x][1]] = x;

    if(dis[ch[x][0]] < dis[ch[x][1]])swap(ch[x][0],ch[x][1]);

    dis[x] = dis[ch[x][1]]+1;

    return x;

}

int getf(int x)

{

    while(f[x])x=f[x];

    return x;

}

void pop(int x)

{

    val[x]=-1;

    f[ch[x][0]]=f[ch[x][1]]=0;

    Merge(ch[x][0],ch[x][1]);

}

int main()

{

    int n,m;

    scanf("%d%d",&n,&m);

    dis[0]=-1;

    for(int i=1;i<=n;i++)

        scanf("%d",&val[i]);

    while(m--)

    {

        int op,x,y;

        scanf("%d%d",&op,&x);

        if(op==1)

        {

            scanf("%d",&y);

            if(val[x]==-1||val[y]==-1||getf(x)==getf(y))continue;

            Merge(getf(x),getf(y));

        }

        else

        {

            if(val[x]==-1)puts("-1");

            else

            {

                int p=getf(x);

                printf("%d\n",val[p]);

                pop(p);

            }

        }

    }

    return 0;

}

/***********************

***********************/