笛卡尔树
单调栈始终维护笛卡尔树从根节点一直向右走的整条链。
一般情况下都是基于数组下标建二叉搜索树，基于元素值建堆
Treap 树
不是很重要，理解思想即可。
笛卡尔树模板
int n;
int p[N];
pii stk[N];
int top = 0;
int lson[N] , rson[N];// (key, value) = (二叉搜索树，小根堆)
for(int i = 1; i <= n; i++){pii lst = {-1,-1}; // 记录栈中最晚弹出的结点while(top && p[i] < stk[top].se){lst = stk[top];top--;}if(top){rson[stk[top].fr] = i;}if(lst.fr != -1){lson[i] = lst.fr;}stk[++top] = {i , p[i]};
}
P1377
Q：给定一个序列，按序依次插入构建一棵二叉搜索树。求能形成与该二叉搜索树形态完全相同，且字典序最小的序列。
容易想到，只要这棵二叉搜索树确定了，那么字典序最小的序列一定是该二叉搜索树先序遍历后的结果。然而，如果这棵二叉搜索树极度不平衡（对一个单调递增的序列建二叉搜索树，形成的是一条链），那么建树的复杂度最坏情况下是 \(O(n^{2})\)（每次插入一个结点需要从根开始向下走）。因此不能对原序列暴力建二叉搜索树。
而我们知道，建笛卡尔树时间复杂度是 \(O(n)\) 的，且笛卡尔树关于 \(key\) 是一棵二叉搜索树。因此不妨考虑改造原序列，并对改造后的序列建笛卡尔树。
我们考虑构建关于 \((元素值，插入时间戳)\) 的笛卡尔树：
- 题目要求元素值形成二叉搜索树
- 向正在构建的二叉搜索树插入一个元素，该元素一定作为叶节点，且时间戳最大，因此很显然所有时间戳小的结点一定在时间戳大的结点上方，符合小根堆的性质
而单调栈构建笛卡尔树需要保证二元组按照 \(key\) 升序排序，因此我们先预处理出所有二元组 \((a[i],i)\) 的集合（\(i\) 就是插入时间戳），然后将该集合升序排序，并构建笛卡尔树。最终我们就会得到 基于 \(a[i]\) 形成二叉搜索树 的一棵笛卡尔树。再先序遍历这棵笛卡尔树即可得到答案。
code
笛卡尔树经常用于序列划分，且常常与树形 dp 结合。
CF1748E
Q：给定长度为 \(n\) 的序列 \(a\)，对满足如下条件的、长度也为 \(n\) 的数组 \(b\) 计数：
- \(\forall i \in [1, n], b_{i} \in [1,m]\)；
- 对于 \(\forall 1\leq l \leq r\leq n\)，\(a_{l\backsim r}\) 与 \(b_{l\backsim r}\) 的最左端最大值位置相同
\(n,m \leq 2e5, n\times m \leq 1e6\)。
一个 trick：将原序列按照基于下标是二叉搜索树，基于元素值是大根堆的方式建一棵笛卡尔树（还有一个指定要求：单调栈在加入元素时，在栈顶遇到相同元素时不弹出，直接压入），我们可以得到有关原序列最左端最大值的划分。
如下图所示：
考虑笛卡尔树上的某个结点，该结点对应原序列的某个位置，其左儿子和右儿子对应了该位置两侧的子区间。由于笛卡尔树关于元素值按大根堆组织，因此在该子树表示区间内的最大值一定在这个位置。设在序列 \(b\) 中，该位置取值为 \(k\)，那么左右两侧子区间的最大值必须满足：
- 左侧子区间最大值 \(< k\)
- 右侧子区间最大值 \(\leq k\)
只有这样，才能满足对于该结点子树表示的区间，包含该位置的子区间的最左端最大值位置与其相同。
于是，问题转化为了在笛卡尔树上做树形 dp。具体实现见 code。
code
P6453
Q 见题目链接。
先给出非常有用的两个小结论：
- 在 \(k \times k\) 的方格图中给 \(k\) 个格涂色，保证任意两个涂色的格子不在同一行、同一列，方案数：
证明略。
- 在 \(n \times m\) 的方格图中给 \(k\) 个格涂色（\(n,m \geq k\)），保证任意两个涂色的格子不在同一行、同一列，方案数：
证明：在 $n$ 行中挑出 $k$ 行，$m$ 列中挑出 $k$ 列，交叉形成一个 $k \times k$ 的方格子图，该子问题和 $1$ 相同。
利用笛卡尔树将整个图形进行划分，每个结点代表一个子矩形，然后利用树形 dp 统计方案数。整道题听下来无比吃力，所以先鸽着不补了qwq。。。
code
agc028b
Q 见题目链接。
笛卡尔树思想 结合 概率期望计算。
考虑转换贡献的计算：对于每个 \(A_{i}\)，总共贡献了多少次。
对于整个序列所有 \(n!\) 种方案中的某一种方案，基于选择位置形成二叉搜索树，时间戳形成小根堆，建立笛卡尔树（不真的建出来）。
eg:
结论：对于任意一种方案，每个位置上的元素的贡献次数就是对应笛卡尔树结点的深度。
那么问题就转换成了：求每个位置在 \(n!\) 种方案对应笛卡尔树结点深度之和。
定义位置 \(i\) 在所有方案的笛卡尔树上结点深度的期望 \(E\)。
由期望的定义可知，\(i\) 号结点上方祖先结点的数量 等于 其他 \(n-1\) 个结点是 \(i\) 号结点祖先的概率 之和。
考虑计算 \(j\) 号结点是 \(i\) 号结点祖先的概率：这里只讨论 \(j < i\) 的情况，\(j > i\) 同理。
结论：\(j\) 是 \(i\) 的祖先，当且仅当 j 的时间戳早于 \([j + 1, i]\) 任何一个位置的时间戳。这个可以通过手玩证明必要性，充分性也很显然。
那么对于全部 \(n!\) 种方案，我们只需要考虑 \([j, i]\) 中所有元素的相对顺序，其中 \(j\) 必须在开头。因此概率为：\(\frac{(i-j)!}{(i-j+1)!}\) = \(\frac{1}{i-j+1}\)。
根据上图给出的算式计算即可。具体实现见 code。
code