大家好，又见面了，我是你们的朋友全栈君。
前言
![[学习笔记]笛卡尔树[通俗易懂]](https://img2018.cnblogs.com/blog/1399631/201902/1399631-20190214111926751-1855431752.png)
![[学习笔记]笛卡尔树[通俗易懂]](https://javaforall.net/wp-content/uploads/2020/11/2020110817443450.jpg)
符合：祖先权值优先级更高，中序遍历是序列本身
类比treap，只不过不平衡
既然不如treap平衡，支持操作就少了。
那么支持的操作，复杂度必须要更优了。
建树
增量法
i=1~n
用单调栈维护最右边路径上的点
加入i点，从底向上找到第一个能放的位置，放上去，从栈中弹出的链就是左儿子。
中序遍历性质显然可以保证
权值优先级显然可以保证
O(n)
（所以Treap也可以O(n)建树）
例题：
![[学习笔记]笛卡尔树[通俗易懂]](https://img2018.cnblogs.com/blog/1399631/201902/1399631-20190214112334828-541617456.png)
求最大矩形
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”的两个性质
对于需要支持操作比较简单的题目，尤其对于序列上有关大小的问题，笛卡尔树的优秀结构可以使得处理有计可施
转载于:https://www.cnblogs.com/Miracevin/p/10373626.html
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/107015.html原文链接：https://javaforall.net
