前置知识：二叉树表示法，二叉搜索树与小根堆的定义。

笛卡尔树

笛卡尔树是一种二叉树，每一个结点由一个二元组 $(a, b)$ 构成。要求 $a$ 满足二叉搜索树的性质，而 $b$ 满足堆的性质。如果笛卡尔树的 $a, b$ 键值确定，且 $a$ 互不相同，$b$ 互不相同，那么这个笛卡尔树的结构是唯一的。

这是一颗笛卡尔树：

笛卡尔树的建树

如果我们提前把 $a$ 从小到大排序，因为 $a$ 满足二叉搜索树的性质，所以每次插入节点都只会在右链上插入。（右链指从根一直往右子树走的路径）

下面的图描述了笛卡尔树建树的过程（红框框起来的是右链，绿点是当前插入的点）。

根据小根堆的定义（$b$ 值满足小根堆性质），右链上的节点的 $b$ 值满足从根往下单调上升，可以用单调栈维护，时间复杂度为 $O(n)$。

模板题代码：

#include <cctype>
#include <cstdio>

int n, a[10000001], s[10000001], t, l[10000001], r[10000001];
long long ans1, ans2;
bool flg = 0;
inline int read(){
	int x = 0;
	char c = getchar();
	while (!isdigit(c)) c = getchar();
	while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
	return x;
}
int main(){
	n = read();
	for (int i = 1;i <= n;i ++) a[i] = read();
	for (int i = 1;i <= n;i ++){
		flg = 0;
		if (t && a[s[t]] > a[i]) flg = 1;
		while (t && a[s[t]] > a[i]) t --;
		if (t) r[s[t]] = i;
		if (flg) l[i] = s[t + 1];
		s[++ t] = i;
	}
	for (int i = 1;i <= n;i ++) ans1 ^= 1ll * i * (l[i] + 1), ans2 ^= 1ll * i * (r[i] + 1);
	printf("%lld %lld", ans1, ans2);
}

笛卡尔树的应用

Treap 线性建树

我们常用的 Treap 也是笛卡尔树的一种，只不过为了保证期望 $\log n$ 的高度，$b$ 的值是完全随机的。所以，如果 $a$ 已经排好序，我们可以使用同样的方法线性建 Treap。

问题的转化

例题：[TJOI2011] 树的序

先插入左儿子还是先插入右儿子对最终建好的 BST 的形态没有影响，但是父亲一定要在儿子之前插入。根据二叉搜索树的定义，一个节点的左儿子比右儿子小，所以建好一颗 BST 输出前序遍历即可。但是建 BST 的时间复杂度为 $O(n^2)$。我们可以将 $a$ 值直接赋值为排列，$b$ 值赋值为插入顺序，再将 $a$ 排序（可以用桶排），建出笛卡尔树，输出前序遍历，时间复杂度为 $O(n)$。

例题：最大的矩形

我们可以将 $i$ 作为 $a$，矩形的高度 $h_i$ 作为 $b$，构建一颗笛卡尔树。

然后我们枚举每一个 $h_u$ 作为矩形的高度。

根据二叉搜索树的性质，笛卡尔树上 $u$ 的子树内所有节点的 $a$ 值属于一个连续的区间。

根据小根堆的性质，笛卡尔树上 $u$ 的子树所有节点的 $b$ 值都大于 $h_u$。所以，我们可以枚举所有 $u$，矩形的高度为 $h_u$，设笛卡尔树上 $u$ 的子树大小为 $siz_u$，矩形的宽度则为 $siz_u$，矩形的面积为 $h_u \times siz_u$。

处理出 $siz_u$ 直接枚举答案即可。

例题：[COCI2008-2009#4] PERIODNI

还是棘手的直方图，我们可以考虑将直方图转化成笛卡尔树，然后在笛卡尔树上跑 DP。

设 $f_{u, i}$ 为以 $u$ 为根的子树中放 $i$ 个车的方案数，

设 $g_{u, i}$ 为以 $u$ 为根的子树中，$u$ 节点（也就是 $u$ 节点所在的小矩形内）不放任意一个车的方案数。

转移方程是这样的：

$g_{u, i} = \sum_{j = 0}^i f_{ls, j} \times f_{rs, i - j}$

$f_{u, i} = \sum_{j = 0}^i g_{u, j} \times C_{h_u - h_{fa}}^{i - j} \times C_{siz_u}^{i - j} \times (i - j)!$

时间复杂度为 $O(n^2k)$。