笛卡尔树学习笔记

本文主要是介绍笛卡尔树学习笔记，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

笛卡尔树本质是一种 \(treap\)，可以线性构建，在构造数据下并不平衡
对于一个排列，其笛卡尔树 \(dfs\) 序为下标，其权值满足小（大）根性质
笛卡尔树可以很好地把序列问题转化为树上问题，其好处在于很方便地利用树上左右子树大小进行处理

笛卡尔树与数列的对应关系：

• 区间 \(RMQ\) 对应笛卡尔树上的 \(LCA\)
• 序列上当前值为最大值的区间大小为笛卡尔树上子树大小
• 笛卡尔树上节点在节点左边的祖先个数为序列上之前大于权值的数的个数

RMQ Similar Sequence

首先，根据前面的性质，比节点大的区间是子树大小
那么恰好相同的概率是 \(\displaystyle\frac{1}{\prod siz_i}\)
一个让人十分震惊的事情是节点的权值期望为 \(\frac{1}{2}\)，于是总和的期望为 \(\frac{n}{2}\)，于是这题就这样草率的完了

• 随机选取可以直接让权值期望为 \(\frac{1}{2}\)

SPOJ PERIODNI

一个以前见过的笛卡尔树经典题，这个题中使用笛卡尔树的优势变得非常明显
首先由于题目中说纵向分隔是互不影响的，那么相当于可以像切片一样把序列分成一层一层的小矩形
比如样例，分成 \(5\times1\)，\(2\times1\)，\(1\times1\)，\(2\times1\)，以及 \(1\times2\) 的矩形即可
这样可以直接在高度上建立笛卡尔树
考虑笛卡尔树上 \(dp\)，进行树形背包
设 \(f[i][j]\) 表示以 \(i\) 为根的子树内放置 \(j\) 个车的方案数
那么 \(f[u][i]=\sum f[v][j]\times f[u][i-j]\) 这个式子是背包常见形式
一个很关键的是在当前所划分出来的矩形里面放点的方案数
考虑在一个 \(a\times b\) 的矩形里放 \(k\) 个点的方案数为 \(\binom{i}{k}\binom{j}{k}k!\)
于是在自己做一遍 \(dp\)

Kcats

这篇关于笛卡尔树学习笔记的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！