左偏树

luogu3377

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
#include<queue>
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
int readint(){
    int ans=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        ans=ans*10+c-'0';
        c=getchar();
    }
    return f*ans;
}
const int maxn=100009;
int n,m;
struct node;
node*merge(node*A,node*B);
struct node{
    int w,d;
    node*l,*r,*f;
    node():w(0),l(NULL),r(NULL),f(NULL){}
    node*get_root(){
        node*x=this;
        while(x->f!=NULL) x=x->f;
        return x;
    }
    void pop(){
        w=-1;
        if(l!=NULL) l->f=NULL;
        if(r!=NULL) r->f=NULL;
        merge(l,r);
    }
}pool[maxn];
node*merge(node*A,node*B){
    if(A==NULL) return B;
    if(B==NULL) return A;
    if(A->w>B->w||(A->w==B->w&&(A-pool>B-pool))) swap(A,B);
    A->r=merge(A->r,B);
    A->r->f=A;
    if(A->l==NULL||A->l->d<A->r->d) swap(A->l,A->r);
    A->d=(A->r==NULL?0:A->r->d+1);
    return A;
}
int main(){
    //std::ios::sync_with_stdio(false);
    //freopen("#test.in","r",stdin);
    //freopen("#test.out","w",stdout);
    n=readint();m=readint();
    for(int i=1;i<=n;i++) pool[i].w=readint();
    while(m--){
        int opt=readint();
        if(opt==1){
            int A=readint(),B=readint();
            if((pool+A)->w==-1||(pool+B)->w==-1) continue;
            if(A==B) continue;
            merge((pool+A)->get_root(),(pool+B)->get_root());
        }else{
            int X=readint();
            if((pool+X)->w==-1){
                puts("-1");
                continue;
            }
            node*t=(pool+X)->get_root();
            printf("%d
",t->w);
            t->pop();
        }
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}