左偏树模板

题目

测试题目传送门

Code

//By zuiyumeng
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Re register
#define Ms(a,b) memset((a),(b),sizeof(a))
#define Fo(i,a,b) for(Re int i=(a),_=(b);i<=_;i++)
#define Ro(i,a,b) for(Re int i=(b),_=(a);i>=_;i--)
using namespace std;

inline int read() { 
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}
    while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();
    return x*f;
}

const int N=1e5+10;
int n,m;
int fa[N],nd[N][2],dis[N],val[N]; // 
bool deld[N]; //是否删除过 1表示已删除

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

#define ls nd[x][0]
#define rs nd[x][1]
int merge(int x,int y) {
    if(!x||!y) return x+y;
    if(val[x]>val[y]) swap(x,y);
    if(val[x]==val[y]&&x>y) swap(x,y);//题目要求：最小值相同时优先删除编号最小的
    fa[rs=merge(rs,y)]=x;
    if(dis[ls]<dis[rs]) swap(ls,rs);
    dis[x]=dis[rs]+1;
    return x;
}

int main() {
    n=read(); m=read();
    dis[0]=-1; //代表所有空点的dis值为-1，因为nd[]初始全为0
    Fo(i,1,n) val[i]=read(),fa[i]=i;
    Fo(i,1,m) {
        int opt=read();
        if(opt==1) {
            int x=read(),y=read();
            if(deld[x]||deld[y]) continue;
            int rx=getro(x),ry=getro(y);
            if(rx==ry) continue;
            fa[rx]=fa[ry]=merge(rx,ry);
        } else {
            int x=read(); 
            if(deld[x]) {cout<<"-1"<<endl;continue;}
            x=getro(x);
            cout<<val[x]<<endl;
            deld[x]=1; //简单的删除操作
            fa[x]=fa[ls]=fa[rs]=merge(ls,rs);//由于使用了路径压缩，有很多点fa[]值为x，所以不如直接fa[x]=新根
        }
    }
    return 0;
}