左偏树,顾名思义,往左偏的树,也就是左子树的大小大于或等于右子树的大小。
还有一些辅助的东西
外节点:没有右儿子或左儿子的点,称为外结点。
左偏树的性质:
- 小根堆的性质,即根节点的值小于左右儿子的值。
- 左偏性质,左子树大小永远大于或等于右子树。
根据这两个性质,又有两个结论
- 对于当前结点$x$,记$dis_x$为$x$到最近的外结点的距离,有$dis_x=dis_{rc}+1$。
- 若根节点的$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;
}
最后一次更新于2020-03-30
0 条评论