左偏树

一种可以合并的堆

前置知识

dist

对于一棵二叉树，我们定义 外节点 为左儿子或右儿子为空的节点，定义一个外节点的 为 ，一个不是外节点的节点 为其到子树中最近的外节点的距离加一。空节点的dist为0。

那么左偏树就是一颗满足堆的性质的二叉树，它的左儿子的dist大于等于右儿子的

核心

核心操作是合并，合并到时候，要满足堆得性质，对于小根堆，就把较小的根作为新的根节点，然后递归合并右儿子和另外一个堆。如果不满足左偏性质，还要交换一下儿子。

int merge(int x,int y){
    if(!x||!y) return x+y;
    if(el[y]<el[x]) swap(x,y);
    el[x].r=merge(el[x].r,y);
    if(dis[el[x].l]<dis[el[x].r]) swap(el[x].l,el[x].r);
    dis[x]=dis[el[x].r]+1;
    return x;
}

插入

把一个单独的节点看成一个堆

删除堆顶

把堆顶的左右儿子合并，并且处理一下信息.

为了快速知道堆顶是谁，我们需要搞一个并查集，并且维护他，删除堆顶的时候要

rt[el[x].l]=rt[el[x].r]=rt[x]=merge(el[x].l,el[x].r);

因为我们要路径压缩，不然太慢了

删除任意元素

删除的时候首先合并左右儿子，把左右儿子形成的新堆合并后接到爹上。

注意要维护dist，可以选择（上面可以）把dist大的当成左儿子，然后合并，这样还不用交换了。

维护整体操作

和线段树差不多，打标记，合并就可以

模板题

#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<stack>
#include<algorithm>
using namespace std;
template<class T>inline void read(T &x)
{
    x=0;register char c=getchar();register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    if(f)x=-x;
}
template<class T>inline void print(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar('0'+x%10);
}
int n;
int m;
struct e{
    int v;
    int id;
    int l;
    int r;
    friend bool operator <(e x,e y){
        return x.v==y.v?x.id<y.id:x.v<y.v;
    }
}el[100005];
int dis[100005];
int rt[100005];
int f;
int x,y;
int del[100005];

int find(int x){
    return x==rt[x]?x:rt[x]=find(rt[x]);
}
int merge(int x,int y){
    if(!x||!y) return x+y;
    if(el[y]<el[x]) swap(x,y);
    el[x].r=merge(el[x].r,y);
    if(dis[el[x].l]<dis[el[x].r]) swap(el[x].l,el[x].r);
    dis[x]=dis[el[x].r]+1;
    return x;
}
int main(){
    read(n);read(m);
    for(int i=1;i<=n;++i){
        read(el[i].v);
        el[i].id=i;
        rt[i]=i;
    }
    for(int i=1;i<=m;++i){
        read(f);
        if(f==1){
            read(x);read(y);
            int xx=find(x);
            int yy=find(y);
            if(del[x]||del[y]||xx==yy){
                continue;
            }
            rt[xx]=rt[yy]=merge(xx,yy);
        }else{
            read(x);
            if(del[x]){
                cout<<"-1n";continue;
            }

            x=find(x);
            del[x]=1;
            cout<<el[x].v<<endl;
            rt[el[x].l]=rt[el[x].r]=rt[x]=merge(el[x].l,el[x].r);
            el[x].l=el[x].r=dis[x]=0;
        }
    }
    return 0;
}