可并堆学习笔记

可并堆就是支持快速合并的堆。

某些时候用这个东西可能会少一个 $log$。

阅读一般的二叉堆合并代码：

int merge(int x,int y)
{
    if(x==0||y==0) return x+y;
    if(tr[x].val>tr[y].val) swap(x,y);
    if(...) tr[x].ls=merge(tr[x].ls,y);
    else tr[x].rs=merge(tr[x].rs,y);
    return x;	
}

注意到由于只需要维护堆的性质，所以 $y$ 和 $x.ls$ 或者 $x.rs$ 中任意一个合并都是可行的。

不难发现，合并会停止当且仅当 $x$ 和 $y$ 其中一个为空节点。那么在每个节点处维护它到子树内最近的空节点（即最近的缺左/右儿子的左/右儿子）的距离 $dist$，每次往 $dist$ 小的儿子递归。

由于 $dist=x$ 的节点子树大小至少为 $2^{x-1}$，所以 $dist$ 是 $\log$ 级别的。

那么单次合并的时间复杂度也就是一个 $\log$ 的了。

为了方便实现，不妨钦定左儿子 $dist$ 较小。

合并代码如下：

inline void upda(int u)
{
    int &ls=tr[u].ls,&rs=tr[u].rs;
    if(tr[ls].dist>tr[rs].dist) swap(ls,rs);
    tr[u].dist=tr[ls].dist+1;
}
int merge(int x,int y)
{
    if(x==0||y==0) return x+y;
    if(tr[x].val>tr[y].val) swap(x,y);
    tr[x].ls=merge(tr[x].ls,y);
    upda(x);
    return x;	
}

有了合并操作，其它操作都是 Ordinary 的，时间复杂度都只有一个 $\log$，常数也比较小。

封装板子：

template<typename T,int siz>
class LTree
{
	private:
		struct node
		{
			T val;
			int dist,ls,rs;
		}tr[siz];
		int tot;
		inline int nnde(T val)
		{
			tr[++tot]={val,1,0,0};
			return tot;
		}
		inline void upda(int u)
		{
			int &ls=tr[u].ls,&rs=tr[u].rs;
			if(tr[ls].dist>tr[rs].dist) swap(ls,rs);
			tr[u].dist=tr[ls].dist+1;
		}
		int merge(int x,int y)
		{
			if(x==0||y==0) return x+y;
			if(tr[x].val>tr[y].val) swap(x,y);
			tr[x].ls=merge(tr[x].ls,y);
			upda(x);
			return x;	
		}
	public:
		inline void clear()
		{
			tr[tot=0]=(node){T(),0,0,0};
		}
		inline void ins(int &rt,T x)
		{
			rt=merge(rt,nnde(x));
		}
		inline T top(int rt)
		{
			return tr[rt].val;
		}
		inline void pop(int &rt)
		{
			rt=merge(tr[rt].ls,tr[rt].rs);
		}
		inline void meg(int &x,int y)
		{
			x=merge(x,y);
		}
};