左偏树

提前说明：下方的做法的dist是将很多讲解中的dist+1后得到的，以避免初始化和比较的麻烦

#include<iostream>
#include<algorithm>
#include <numeric>

#define N 100005
#define ls(x) (tr[x].l)
#define rs(x) (tr[x].r)
#define dist(x) (tr[x].dist)
#define val(x) (tr[x].v)
#define int long long
using namespace std;


struct NODE{
    int fa,l,r,v,dist;
} tr[N];
int &rson(int x){
    return tr[ls(x)].dist>tr[rs(x)].dist?rs(x):ls(x);
}
int find(int x){
    return tr[x].fa==x?x:(tr[x].fa=find(tr[x].fa));
}
int merge(int x,int y){
    if(!x||!y) return x|y;
    if(val(x)>val(y)||(val(x)==val(y)&&x>y)) swap(x,y);
    tr[rs(x)=merge(rs(x),y)].fa=x;
    if(dist(ls(x))<dist(rs(x))){
        swap(ls(x),rs(x));
    }
    dist(x)=dist(rs(x))+1;
    return x;
}
int n,m;
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>tr[i].v,tr[i].fa=i,tr[i].dist=1;
    for(int i=1;i<=m;i++){
        int opt,x,y;
        cin>>opt;
        if(opt==1){
            cin>>x>>y;
            if(!dist(x)||!dist(y)) continue;
            int tx=find(x),ty=find(y);
            if(tx!=ty) merge(tx,ty);
        }else{
            cin>>x;
            if(!dist(x)){
                cout<<"-1\n";
            }else{
                int root=find(x);
                cout<<val(root)<<"\n";
                dist(root)=0;
                tr[root].fa=tr[ls(root)].fa=tr[rs(root)].fa=merge(ls(root),rs(root));
            }
        }
    }
}

被这道题卡了好久

最后发现，我根本不会并查集
为什么这么说呢？大家可能都清楚并查集的用处，路径压缩，启发式合并，菊花图，但是事实上并查集有很多细节
比如说这道题，带删除的，就会使并查集的路径压缩失效。那怎么处理呢？就是把被删除的节点的父亲指向自己的儿子，也就是回溯

这道题还有很多细节值得推敲，比如把dist置0作判断是否存在的条件，merge前先检查
本来写的是动态计算右儿子的做法，但是最后觉得不好调试就改了