前言
堆与可删除堆已经是烂大街的数据结构了,毒瘤的出题人从而考虑从左偏树下手,也就是俗称的可合并堆
性质
我们新定义一个节点的距离为到最近叶子节点的距离
\(1、\)左儿子距离\(≥\)右儿子,左偏就是这个意思\(2、\)节点距离等于右儿子距离\(+1\)(显然)\(3、\)节点距离是\(log\)级别的(显然)前置
堆本质是维护一个集合里特定值,既然是个集合,并查集查询位置是必不可少的(压缩)
合并
左偏树唯一的好处就是能快速合并,而既然距离是\(log\)级别的,所以合并自然要利用右儿子/距离
流程:不断确定当前根,右儿子递归下去合并,非满集时继承
LL Merge(LL x,LL y){ if(!x || !y) return x+y; if(val[x]>val[y] || (val[x]==val[y] && y
删除
删除的标志是值为\(-1\)
最后一句有点奇怪:压缩路径后原本指向\(x\)的位置我们需要通过已删除点作为媒介(最后的用途)指向新集标号
inline void pop(LL x){ val[x]=-1; f[son[x][0]]=son[x][0]; f[son[x][1]]=son[x][1]; f[x]=merge(son[x][0],son[x][1]);}