一种二叉树，主要用于解决有关序列 $\text{RMQ}$ 问题和直方图问题，建树时间复杂度 $O(n)$。

笛卡尔树具有如下三条性质：

1. 对笛卡尔树中序遍历可以得到原序列
2. 笛卡尔树的点权符合堆性质
3. 任意区间的 $\text{RMQ}$ 操作可以转换为笛卡尔树上两端点的 $\text{LCA}$ 操作

接下来考虑建树，事实上可以按顺序插入序列，每次插入时由于插入结点下标最大，所以只能不停跳右子树。

找到合适结点，取代该结点位置，并将该结点所在子树变成插入结点的左子树。

发现只需要用一个单调栈维护一下从根结点起沿途所有右儿子构成的树链即可，时间复杂度 $O(n)$。

洛谷p5854

const int MAXN=1e7+5;
int Stack[MAXN],v[MAXN],ch[MAXN][2];
void build(int n){//小根堆的笛卡尔树 
	int top=0,last=0;
	_rep(i,1,n){
		while(top&&v[i]<v[Stack[top]])top--;
		if(top)ch[Stack[top]][1]=i;
		if(top<last)ch[i][0]=Stack[top+1];
		Stack[++top]=i;
		last=top;
	}
}

SP3734

给定一个 $N$ 列的表格，每列的高度为 $a_i$ 且底部对齐。

要求向表格中填入 $k$ 个相同的数，填写时要求不能有两个数在同一列，或在同一行且中间表格不间断。

问在取模意义下有多少种填法。

建立根据表格高度建立笛卡尔树，将表格划分分 $N$ 个矩形。

设 $f(i,j)$ 表示在以结点 $i$ 为根结点的子树所代表的区域中填写 $j$ 个数的填法种数。

设 $g(i,j)$ 表示在以结点 $i$ 为根结点的子树所代表的区域中填写 $j$ 个数且不在根结点代表的矩形填写数字的填法种数。

再在考虑从该结点所代表的矩阵中选取 $k$ 个结点所产生的贡献。

从 $n\times m$ 的矩阵中选取 $k$ 个结点的总数为 $k!C_n^kC_m^k$，预处理 $k!$ 和 $k!$ 的逆即可快速求出。