左偏树第一题，纪念一下
大概讲一下左偏树吧。。
首先它是一个可以合并的堆，因此是可并堆的一种
什么叫可以合并呢
就是说现在给你两个堆，我现在要你将他们合并起来，变成一个新的堆
要是一般的写法我们是要讲所有数拿出来，再重新插进去
但很显然这样的时间是过不去的。。
于是就有了这个东西
至于可并堆别的实现方法，(⊙v⊙)嗯，还不会。。
至于为什么叫左偏树呢，就是因为他左偏的性质
左偏啊，就是说左边的“值”大
这里的“值”是什么呢，我们规定：
节点i称为外节点(external node)，当且仅当节点i的左子树或右子树为空 ( left(i) = NULL或right(i) = NULL )；节点i的距离(dist(i))是节点i到它的后代中，最近的外节点所经过的边数。特别的，如果节点i本身是外节点，则它的距离为0
而左偏的性质就是
节点的左子节点的距离不小于右子节点的距离。
可以证明：这样下来一棵N个节点的左偏树距离最多为log(N+1) -1
因为这样的话最差情况就是一颗满二叉树嘛
这就是左偏树时间复杂度的保证
接着我们合并的时候可能会使左偏树变为一颗右偏树，那么我们只需要将他们的左右儿子交换就可以了。。
至于怎么搞，大家可以看看代码，接着自己弄几个栗子模拟一下，我这里就不给图了
要是实在想看的朋友，看一去看05年黄源河的论文
然后呢这一题就是一到裸题了。。
我这里给出一个左偏树的模板，大家也可以参考:
#include<cstdio>
#include<cstring>
#define swap(x,y) {int tt=x;x=y;y=tt;}
const int N=1000005;
int n,m;
int v[N];
bool del[N];//这个点还存不存在
int f[N];
int d[N];//这个节点到外节点的最短距离
int l[N],r[N];//左右节点
int find (int x){
return f[x]==x?f[x]:f[x]=find(f[x]);}
int Merge (int x,int y)
{if (x==0) return y;if (y==0) return x;if (v[x]>v[y]) swap(x,y);//保证x可以做根r[x]=Merge(r[x],y);if (d[r[x]]>d[l[x]]) swap(r[x],l[x]);d[x]=d[r[x]]+1;return x;
}
int main()
{memset(d,0,sizeof(d));memset(del,false,sizeof(del)); d[0]=-1;//保证当x没有孩子是他是0 scanf("%d",&n);for (int u=1;u<=n;u++) f[u]=u;for (int u=1;u<=n;u++) scanf("%d",&v[u]);scanf("%d",&m);while (m--){char ss[5];scanf("%s",ss);if (ss[0]=='M'){int a,b;scanf("%d%d",&a,&b);if (del[a]==true||del[b]==true) continue;int tx=find(a),ty=find(b);if (tx==ty) continue;int t=Merge(tx,ty);f[tx]=f[ty]=t;}else{int a;scanf("%d",&a);if (del[a]==true) {
printf("0\n");continue;}int tx=find(a);del[tx]=true;printf("%d\n",v[tx]);f[tx]=Merge(l[tx],r[tx]);f[f[tx]]=f[tx];}}return 0;
}