笛卡尔树学习笔记

笛卡尔树是一种特殊的二叉树，它的每个节点有两个权值 $k_i$ 和 $w_i$。对于权值 $k_i$，满足二叉搜索树的特性，即父节点的 $k_i$ 严格大于它左儿子的 $k_i$，它右儿子的 $k_i$ 又严格大于它的 $k_i$。而对于权值 $w_i$，满足小根堆的特性，即父节点的 $w_i$ 小于等于它儿子的 $w_i$。

例如下图就是一棵 $w_i$ 为圆圈里的数的笛卡尔树。

考虑笛卡尔树的构建。首先对 $k_i$ 排过序，那么新加进来的节点肯定在右链上（右链即从根节点一直往右儿子去所形成的链）。此时可以使用单调栈来维护右链，进行 $O(n)$ 的建树。

建树过程类似下图（圆圈里的数为 $w_i$）：

建树代码：

sta[++top]=1;
for(int i=2;i<=n;i++)
{
	while(w[sta[top]]>w[i]&&top>0)
	{
		top--;
	}
	if(top==0)
	{
		son[i][0]=sta[top+1];
	}
	else
	{
		son[i][0]=son[sta[top]][1];
		son[sta[top]][1]=i;
	}
	sta[++top]=i;
}

练习题目：

• P5854 【模板】笛卡尔树

• P1377 [TJOI2011]树的序

• SP3734 PERIODNI - Periodni

• P6453 [COCI2008-2009#4] F

• P7988 [USACO21DEC] HILO G