左偏树是一种数据结构，又称可并堆。它可以用于支持多个大/小根堆的合并。在以前我们都使用priority_queue来维护一个堆中的最大/小值，但是这只能维护单点的情况。有了左偏树之后，我们就可以支持把多个小根堆都合并到一起的操作了。
基础的左偏树可以支持如下操作：把数x，y所在的堆合并。
返回数x所在的小根堆的最小值。
插入或删除节点。
在开始之前我们先说一下左偏树的性质。
性质1：节点的权值小于等于其左右节点的权值。(堆的性质)
性质2：节点到左儿子的距离不小于节点到右儿子的距离。注意这里的距离并不是指权值或是深度，在写平衡树的时候，我们是确保它的深度尽量的小，这样访问每个节点都很快。但是左偏树不需要这样，它的目的是快速提取最小节点和快速合并。所以它并不平衡，而且向左偏。但是距离和深度不一样，左偏树并不意味着左子树的节点数或是深度一定大于右子树。（copy自luogu题解）；
性质3：节点距离等于右儿子距离+1；
性质4：一棵n个节点的左偏树距离最大为log（n+1） - 1；
那我们开始。首先是合并操作。在合并的时候，我们选取要合并的两个节点A,B，之后把A的根作为合并之后的新堆的根，再把B的子树与A的右子树合并即可。
（注意这里要设A的根小于B的根，否则交换他们）
合并了A的右子树和B之后，A的右子树的距离可能会变大，当A的右子树 的距离大于A的左子树的距离时，性质2会被破坏。在这种情况下，我们只须要交换A的右子树和左子树。
而且因为A的右子树的距离可能会变，所以要更新A的距离=右儿子距离+1。这样就合并完了。
之后插入和删除都是常规操作了，插入一个点就是把一个点和一个小根堆合并，而删除的话就是把节点自己剔除出去，再把他的左右子树合并即可。
至于如何找到一个根中的最小值，我们可以直接使用并查集维护，在每次递归返回更新的时候更新一次每个节点的父亲即可。
上代码。
#include<cstdio> #include<algorithm> #include<iostream> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int N = 100005; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } int m,n,v[N],lc[N],rc[N],dis[N],op,fa[N],x,y; int merge(int x,int y) { if(!x || !y) return x | y;//如果两个节点中右任意一个不存在，返回存在的点即可 if(v[x] > v[y] || (v[x] == v[y] && x > y)) swap(x,y);//交换以满足根最小 rc[x] = merge(rc[x],y);//递归合并A的右子树和B fa[rc[x]] = x;//修改他的父亲 if(dis[lc[x]] < dis[rc[x]]) swap(lc[x],rc[x]);//维护距离以保证左偏树不退化 dis[x] = dis[rc[x]] + 1;//修改距离 return x; } int getfa(int x)//找父亲操作 { while(fa[x]) x = fa[x]; return x; } void del(int x)//删除操作 { v[x] = -1;//把这个点的值设为不存在 fa[lc[x]] = fa[rc[x]] = 0;//设为左右子树不存在 merge(lc[x],rc[x]);//把其左右子树合并 } int main() { n = read(),m = read(); dis[0] = -1; rep(i,1,n) v[i] = read(); rep(i,1,m) { op = read(); if(op == 1) { x = read(),y = read(); if(v[x] == -1 || v[y] == -1) continue; if(x == y) continue;//如果不存在就忽略 int r1 = getfa(x); int r2 = getfa(y); merge(r1,r2);//用并查集找到堆中最小值并合并 } else { x = read(); if(v[x] == -1) printf("-1 "); else { int r1 = getfa(x); printf("%d ",v[r1]); del(r1);//找到最小值并删除 } } } return 0; } /* 5 5 1 5 4 2 3 1 1 5 1 2 5 2 2 1 4 2 2 2 */