详细见代码注释
int& rs(int x)//求右儿子
{
return t[x].ch[t[t[x].ch[1]].d<t[t[x].ch[0]].d];//为了满足左偏树的性质2,须保证右子树节点的dist小于左子树节点的dist
}
int merge(int x,int y)//合并x,y
{
if(!x||!y)return x+y;
if(t[x].val>t[y].val)swap(x,y);//这个根据所须的左偏树是大根堆还是小根堆,这里是小根堆,反过来是大根堆
rs(x)=merge(rs(x),y);//将右子树与y合并
f[rs(x)]=x;//当需要更新父亲时加上
t[x].d=t[rs(x)].d+1;//满足左偏树的性质3
return x;
}
找到\(x\)所在堆的最小值/最大值,用并查集实现,接着合并\(x\)的左右子树
int find(int x){x==f[x]?x:f[x]=find(f[x]);}
void pop(int &x)
{
x=find(x)//找到x所在堆的最大值/最小值
x=merge(t[x].ch[0],t[x].ch[1]);//合并左右儿子
}
注意:这里是删除任意编号节点,而不是任意权值节点,左偏树不支持删除任意权值节点
我们先合并\(x\)的左右儿子
接着更新\(x\)的父亲和\(f[x]\)的儿子
因为这样合并更新可能会破坏左偏的性质,所以需要遍历检查满不满足左偏性质,更新,直到满足左偏性质就可以结束或者到达根节点
void pushup(int x)
{
if(!x)return ;//达到根节点,返回
if(t[x].d!=t[rs(x)].d+1)//不满足左偏性质,更新
{
t[x].d=t[rs(x)].d+1;
pushup(f[x]);
}
}
int merge(int x,int y)
{
if(!x||!y)return x|y;
if(t[x].val>t[y].val)swap(x,y);
f[rs(x)=merge(rs(x),y)]=x;
pushup(x);
return x;
}
void del(int x)
{
int fx=f[x];//x的父亲
int u=merge(t[x].ch[0],t[x].ch[1]);//合并左右儿子
f[u]=fx;//更新合并后的节点的信息
if(t[fx].ch[0]==x)t[fx].ch[0]=u;
else t[fx].ch[1]=u;
t[x].val=t[x].ch[0]=t[x].ch[1]=t[x].d=0;
pushup(x);//遍历检查左偏性质
}
新建一个节点,将其初始化为\(x\)
因为这个节点也可以视为一个堆,可以直接合并
void push(int &rt,int v)
{
t[++cnt].val=v;
t[cnt].ch[0]=t[cnt].ch[1]=t[cnt].d=0;
rt=merge(rt,cnt);
}
在根\(x\)上打标记,然后每一次合并堆或者删除根时下传
void pushdown(int x)//这里以加上一个数为例
{
if(lazy[x])
{
t[ch[x].ch[0]].val+=lazy[x];
t[ch[x].ch[1]].val+=lazy[x];
lazy[ch[x].ch[0]]+=lazy[x];
lazy[ch[x].ch[1]]+=lazy[x];
lazy[x]=0;
}
}
给出洛谷P2713 罗马游戏的代码
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
struct Tree
{
int val,ch[2],d;
}t[N];
int n,q;
int f[N];
bool dead[N];
int& rs(int x)
{
return t[x].ch[t[t[x].ch[1]].d<t[t[x].ch[0]].d];
}
int merge(int x,int y)
{
if(!x||!y)return x|y;
if(t[x].val>t[y].val)swap(x,y);
f[rs(x)=merge(rs(x),y)]=x;
t[x].d=t[rs(x)].d+1;
return x;
}
int find(int a)
{
return a==f[a]?a:f[a]=find(f[a]);
}
char op[10];
int main()
{
scanf("%d",&n);
int a,b;
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
t[i].val=a;
f[i]=i;
}
scanf("%d",&q);
while(q--)
{
scanf("%s",op);
if(op[0]=='M')
{
scanf("%d %d",&a,&b);
int fx=find(a),fy=find(b);
if(dead[a]||dead[b]||fx==fy)continue;
f[fx]=f[fy]=merge(fx,fy);
}
else
{
scanf("%d",&a);
if(dead[a])
{
puts("0");
continue;
}
a=find(a);
dead[a]=1;
f[a]=f[t[a].ch[0]]=f[t[a].ch[1]]=merge(t[a].ch[0],t[a].ch[1]);
printf("%d\n",t[a].val);
}
}
return 0;
}
深深感觉到自己的渺小
原文:https://www.cnblogs.com/ShuraEye/p/11379618.html