左偏树，顾名思义，往左偏的树，也就是左子树的大小大于或等于右子树的大小。

还有一些辅助的东西

外节点:没有右儿子或左儿子的点，称为外结点。

左偏树的性质:

  1. 小根堆的性质，即根节点的值小于左右儿子的值。
  2. 左偏性质，左子树大小永远大于或等于右子树。

根据这两个性质，又有两个结论

  1. 对于当前结点$x$，记$dis_x$为$x$到最近的外结点的距离，有$dis_x=dis_{rc}+1$。
  2. 若根节点的$dis$为$n$，则说明左偏树的大小不小于$2^{n+1}-1$，取等仅在左偏树是一棵满二叉树。

结论$2$保证了左偏树的单次操作复杂度为$O(log ~n)$，因为每次修改仅要对右子树进行操作来保持树的基本平衡，如果破坏平衡了，就要交换子树。

对于合并两棵左偏树(可并堆)的操作$merge(x,y)$，

考虑根节点保留$x$还是$y$，为了节省操作不如直接交换，使得$x$的值始终小于$y$。

再把剩下的$y$，传到$x$的右子树进行比较。

进行完这些操作之后，更新根节点$x$的$dis$。

如果子树大小违背了左偏树的性质，则需要交换子树。

对于插入一个点到一棵树中的操作，

直接当做合并操作就可以了。

如果带删点的话，需要快速找到根节点，这就需要多一个并查集来支持快速查询。

但是如果删除一个点$x$，需要改变其所辖的所有节点的路径(并查集)，因此需要将它的父亲也改变为删除$x$后的根节点，来保证正确性。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#define gc getchar()
#define ll long long
#define ld long double 
#define ull unsigned long long
using namespace std;
const int N=1e6+5,M=8555;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int rc[N],lc[N],rt[N],dis[N];
struct node
{
    int id,val;
    bool operator <(const node a)const{return val==a.val?id<a.id:val<a.val;}
}v[N];
int get(int x){return x==rt[x]?x:rt[x]=get(rt[x]);}
int merge(int x,int y)
{
    if(!x||!y)return x+y;
    if(v[y]<v[x])swap(x,y);
    rc[x]=merge(rc[x],y);
    if(dis[rc[x]]>dis[lc[x]])swap(rc[x],lc[x]);
    dis[x]=dis[rc[x]]+1;
    return x;
}
bool vis[N];
int main()
{
    dis[0]=-1;
    int n,m;qr(n),qr(m);
    for(int i=1;i<=n;i++)qr(v[i].val),rt[i]=i,v[i].id=i;
    for(int i=1;i<=m;i++)
    {
        int op,x,y;qr(op);qr(x);
        if(op==1)
        {
            qr(y);
            if(vis[x]||vis[y])continue;
            int px=get(x),py=get(y);
            if(px!=py)rt[px]=rt[py]=merge(px,py);
        }
        else
        {
            if(vis[x]){puts("-1");continue;}
            x=get(x);
            qw(v[x].val);puts("");
            vis[x]=1;
            rt[x]=rt[lc[x]]=rt[rc[x]]=merge(lc[x],rc[x]);
            dis[x]=0;lc[x]=rc[x]=0;
        }
    }
    return 0;
}