1 定义
笛卡尔树是一种二叉树，每一个节点由二元组 \((k,w)\) 组成。要求 \(k\) 满足二叉搜索树的性质，\(w\) 满足堆的性质。
当 \(k,w\) 都确定，且 \(k,w\) 互不相同时，笛卡尔树的结构是唯一的，如图：
看到这个定义，会发现与 Treap 十分相似。
实际上，Treap 就是一种特殊的笛卡尔树。
通常情况下，将下标作为 \(k\)（如上图）。
2 建树
2.1 过程
首先由定义可以直接得出一个 \(O(n\log n)\) 算法，但是重点不在于此。
笛卡尔树有线性的构造方式。
我们先将所有元素按照 \(k\) 排序，那么这样我们按顺序插入的时候，一定是插入到树的右链（即从根节点不断走向右儿子所形成的链）。
那么此时我们观察右链，假设当前节点是 \(p\)，那么现在要满足的就是堆的性质。我们从右链末端开始比较，当出现第一个 \(x\) 满足 \(x_w<p_w\) 时，就将 \(p\) 接到 \(x\) 右儿子上，而 \(x\) 原先的右儿子变为 \(p\) 的左儿子。
如果没有找到这个 \(x\)，那么 \(p\) 就成为了根节点。
现在我们考虑维护右链，因为维护右链的过程中就可以建好树。显然右链的 \(w\) 是要满足单调递增的。那么插入元素的过程中维护一个单调递增的结构，这显然是单调栈。
2.2 代码
有了上面的分析，代码就不难了：
int s[Maxn], top;
for(int i = 1; i <= n; i++) {int k = top;while(k && w[s[k]] > w[i]) k--;if(k) rs[s[k]] = i;if(k < top) ls[i] = s[k + 1];s[++k] = i;top = k;
}
3 用途
笛卡尔树适合解决与最值相关的问题，不过先给出一些性质（以小根堆为例）：
- 以 \(u\) 为根的子树是一段连续的区间，且区间最小值就是 \(u_w\)
- 区间上 \([l,r]\) 的最小值就是 \(\text{Lca}(l,r)_w\)。
- 若 \(y\) 随机，则树高期望为 \(\log\)。（这样做就是 Treap 了）。
下面举一例：
3.1 [例 1] 最大子矩形问题
形式化题意：给定数组 \(a\)，求 \(\max\{\min\limits_{i=l}^r(a_i)\times (r-l+1)\},1\le l\le r\le n\)。
这道题是经典的单调栈题，不过也可以用笛卡尔树。
具体的，我们以下表为 \(k\)，值为 \(w\) 建立笛卡尔树。接下来我们枚举最小值，然后找最小值为它的最长区间。
由上面的性质 \(1\) 得，最长区间就是子树大小，于是两者相乘取最大值即可。
