题解 P3377 【【模板】左偏树（可并堆）】

更多左偏树姿势、例题，欢迎来[blog](http://www.yhzq-blog.cc/左偏树学习总结/) 在学OI的前期，我们接触了一种数据结构，叫做堆。它资瓷插入一个元素，查询最小/大元素和删除最小/大元素。然后就发现STL的$priority \ queue$可以直接用，非常的方便。 但是有时候题目让我们资瓷两个堆的合并，这样$priority \ queue$就不行了(但是pb\_ds还是可以的)。这样我们就要手写左偏树。 什么是左偏树呢？首先，从名字上看，它是一棵树。其实它还是一棵二叉树。它的节点上存4个值：左、右子树的地址，权值，距离。 权值就是堆里面的值。距离表示这个节点到它子树里面最近的叶子节点的距离。叶子节点距离为0。 既然是一种特殊的数据结构，那肯定有它自己的性质。左偏树有几个性质(小根为例)。 > 性质一：节点的权值小于等于它左右儿子的权值。 堆的性质，很好理解。 > 性质二：节点的左儿子的距离不小于右儿子的距离。 在写平衡树的时候，我们是确保它的深度尽量的小，这样访问每个节点都很快。但是左偏树不需要这样，它的目的是快速提取最小节点和快速合并。所以它并不平衡，而且向左偏。但是距离和深度不一样，左偏树并不意味着左子树的节点数或是深度一定大于右子树。 > 性质三：节点的距离等于右儿子的距离+1。 没什么好说的= = > 性质四：一个n个节点的左偏树距离最大为$log(n+1)-1$ 这个怎么证明呢？我们可以一点一点来。 **若左偏树的距离为一定值，则节点数最少的左偏树是完全二叉树。** 节点最少的话，就是左右儿子距离一样，这就是完全二叉树了。 **若一棵左偏树的距离为k，则这棵左偏树至少有$2^{k+1}-1$个节点。** 距离为k的完全二叉树高度也是k，节点数就是$2^{k+1}-1$。 这样就可以证明性质四了。因为$n>=2^{k+1}-1$，所以$k<=log(n+1)-1$ 有了性质，我们来讲讲它的操作。 #### 1.合并 <center></center> 我们假设A的根节点小于等于B的根节点（否则交换A,B），把A的根节点作为新树C的根节点，剩下的事就是合并A的右子树和B了。 <center></center> 合并了A的右子树和B之后，A的右子树的距离可能会变大，当A的右子树 的距离大于A的左子树的距离时，性质二会被破坏。在这种情况下，我们只须要交换A的右子树和左子树。 而且因为A的右子树的距离可能会变，所以要更新A的距离=右儿子距离+1。这样就合并完了。 <center></center> 代码 ```cpp int merge(int x,int y) { if (x==0 || y==0) return x+y; if (val[x]>val[y] || (val[x]==val[y] && x>y)) swap(x,y); ch[x][1]=merge(ch[x][1],y); f[ch[x][1]]=x; if (dis[ch[x][0]]<dis[ch[x][1]]) swap(ch[x][0],ch[x][1]); dis[x]=dis[ch[x][1]]+1; return x; } ``` 我们来分析一下复杂度。我们可以看出每次我们都把它的右子树放下去合并。因为一棵树的距离取决于它右子树的距离(性质三)，所以拆开的过程不会超过它的距离。根据性质四，不会超过$log(n_x+1)+log(n_y+1)-2$，复杂度就是$O(\log n_x+\log n_y)$ #### 2.插入 插入一个节点，就是把一个点和一棵树合并起来。 因为其中一棵树只有一个节点，所以插入的效率是$O(\log n)$ #### 3.删除最小/大点 因为根是最小/大点，所以可以直接把根的两个儿子合并起来。 因为只合并了一次，所以效率也是$O(\log n)$。 代码 ```cpp #include <cstdio> #define N 100010 using namespace std; int inline read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } void swap(int &x,int &y){int t=x;x=y,y=t;} int ch[N][2],val[N],dis[N],f[N],n,m; int merge(int x,int y) { if (x==0 || y==0) return x+y; if (val[x]>val[y] || (val[x]==val[y] && x>y)) swap(x,y); ch[x][1]=merge(ch[x][1],y); f[ch[x][1]]=x; if (dis[ch[x][0]]<dis[ch[x][1]]) swap(ch[x][0],ch[x][1]); dis[x]=dis[ch[x][1]]+1; return x; } int getf(int x) { while(f[x]) x=f[x]; return x; } void pop(int x) { val[x]=-1; f[ch[x][0]]=f[ch[x][1]]=0; merge(ch[x][0],ch[x][1]); } main() { n=read(),m=read(); dis[0]=-1; for (int i=1;i<=n;i++) val[i]=read(); for (int i=1;i<=m;i++) { int com=read(); if (com==1) { int x=read(),y=read(); if (val[x]==-1 || val[y]==-1) continue; if (x==y) continue; int fx=getf(x),fy=getf(y); merge(fx,fy); } else { int x=read(); if (val[x]==-1) puts("-1"); else { int y=getf(x); printf("%d\n",val[y]); pop(y); } } } } ``` 目前效率第一，欢迎超越。