本文共 1902 字，大约阅读时间需要 6 分钟。

左偏树第一题，纪念一下

至于为什么叫左偏树呢，就是因为他左偏的性质

节点i称为外节点(external node)，当且仅当节点i的左子树或右子树为空 ( left(i) = NULL或right(i) = NULL )；节点i的距离(dist(i))是节点i到它的后代中，最近的外节点所经过的边数。特别的，如果节点i本身是外节点，则它的距离为0

而左偏的性质就是

节点的左子节点的距离不小于右子节点的距离。

可以证明：这样下来一棵N个节点的左偏树距离最多为log(N+1) -1

接着我们合并的时候可能会使左偏树变为一颗右偏树，那么我们只需要将他们的左右儿子交换就可以了。。

至于怎么搞，大家可以看看代码，接着自己弄几个栗子模拟一下，我这里就不给图了

然后呢这一题就是一到裸题了。。

#include
   
    #include
    
     #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;}