[学习笔记]笛卡尔树[通俗易懂]

笛卡尔树Cartesian Tree

前言

符合：祖先权值优先级更高，中序遍历是序列本身

类比treap，只不过不平衡

既然不如treap平衡，支持操作就少了。

那么支持的操作，复杂度必须要更优了。

建树

增量法

i=1~n

用单调栈维护最右边路径上的点

加入i点，从底向上找到第一个能放的位置，放上去，从栈中弹出的链就是左儿子。

中序遍历性质显然可以保证

权值优先级显然可以保证

O(n)

（所以Treap也可以O(n)建树）

例题：

求最大矩形

1.单调栈直接做。

2.建立小根堆笛卡尔树，每个点的贡献是：子树sz*高度。正确性显然

例题2：

 bzoj2616: SPOJ PERIODNI——笛卡尔树+DP

例题3：

• 对于任意排列，定义其权值为：
• 首先求出排列的笛卡尔树
• 对于树上有两个儿子的节点，设儿子的下标位置为 ? 和 ?
• 版本一：其对权值的贡献为 |pa-pb|
• 版本二：其对权值的贡献为 |? − ?|
• 假设排列等概率随机，求权值的期望
• ? ≤ 100

两种不同的思路：

版本一：

关心儿子位置，

f[i][j]大小为i的树，根节点在j位置权值

枚举左儿子和右儿子的位置a,b，再分配编号：C(i-1,a)

可以把f[i][a]+a之类放在一起进行前缀和优化

纯粹从计数考虑，还要维护方案数

个数从小到大扩展，位置合并并分配编号

还有相对设法

版本二：

权值绝对值要去掉，从小到大加入

大的树就是放到叶子了

拼接的时候贡献还要考虑父亲权值不好处理

如果有些点必然会有叶子，那么放下一个权值之前，这些位置直接贡献cnt的答案

类似放书那个题

f[i][j][k]放了前i个数，有j个位置还少两个叶子，k个位置还少一个叶子（对未来承诺！）

合并

%%immortalCO

数据结构杂题集第三个有提到

定义关键点：一个树最左边和最右边两个链

关键点只有初始的O(n)个

合并x,y时候，对于x的右链和y的左链，从最底下开始往上找到第一个能放的位置，这一段长度设为len

之后这段关键点会被覆盖住，不再存在。

然后y的这个点左儿子和x的这个点的右儿子进行类似fhq的合并，也就是一般的暴力合并

由于路径上的点就是两个段的关键点

关键点然后就消失了。

走的长度就是关键点减少的个数

所以均摊O(n)

从最底下开始找，可以用链表然后链表合并。单纯记录每个点最右边的点也可以

sz什么的pushup就找到了。

（pushup这个不太好找到，最开始一段链很难搞。可以用LCT同时和笛卡尔树合并做，用于打上标记）

挺trick的

感悟

具有“treap”的两个性质

对于需要支持操作比较简单的题目，尤其对于序列上有关大小的问题，笛卡尔树的优秀结构可以使得处理有计可施