笛卡尔树

· · 算法·理论

确保自己大体了解笛卡尔树。本文包含以下内容：

一些性质

  1. 笛卡尔树的每个子树都是一段连续的区间。

  3. 随机数据下笛卡尔树期望深度 O(\log n)。

笛卡尔树合并

这里指的是随机数据下生成两个数组，同时我们分别有这两个序列的相同最值笛卡尔树，可以做到 O(\log n) 的时间复杂度合并。

由于笛卡尔树本身就是一个 treap 的结构，因此直接按照 treap 一样做就好。不多赘述。实际上用处也不大。

动态维护笛卡尔树

考虑需要修改序列上某个点的权值，维护其笛卡尔树，数据随机。我们直接删去那个点之后按照 BST 的删除合并左右子树，然后再尝试把修改后的数插入进去，实际上和 BST 是一致的。

练习：P2611。

最值分治

传统分治往往是找到区间中点，对两边分治，时间复杂度为 T(n)=T(n/2)+O(n)。而有些问题并不能按照区间中点分治，而是像笛卡尔树一样，找到最值进行分治。

分治能进行在笛卡尔树上的原因主要在于其每个子树都是一个连续的区间，同时从 i 的左右子树各取一点 a 和 b，则 [a,b] 的最大值在 i 处（[a,b] 的最值在它们的 LCA 处）。

最值分治往往会给出一个和区间最值有关的式子要求计数或者最优化，我们枚举这个区间最值，那么区间左右端点就是要在左子树和右子树中各选一个点来满足这个式子，一般我们要是知道了某一个端点就能对另外一个端点计数，但是复杂度一般不允许任意枚举端点，因此对两个子树中大小较小的那个枚举（启发式分治），这样每个点最多会被枚举 O(\log n) 次（类似启发式合并），总的枚举次数也就成了 O(n\log n) 次。

一道板子题

问题本身和最大值有很大的联系，考虑最值分治。建出笛卡尔树，对于一个点 i，考虑从其左子树中选一个点，从右子树中选一个点，会得到多少美丽的数对。由于已经知道了区间最大值是 a_i，因此如果知道了左子树中选出了 j，那么对右子树中选出的 k 就有限制 a_j\times a_k\le a_i\rightarrow a_k\le\lfloor\dfrac{a_i}{a_j}\rfloor，即查询某个区间中有多少小于某个阈值的数，套路地拆成前缀查询后扫描线离线维护，也可以用主席树离散化后在线维护。但是我们不能任意枚举左子树中的点，复杂度可能会退化。用上面提到的启发式分治，枚举大小较小的那个子树，这样每个点只会被枚举 O(\log n) 次，这样也就只会有 O(n\log n) 个区间被查询，时间复杂度 O(n\log^2 n)。

代码。

另一道板子题

这个 \min 看上去很突兀，直接最值分治。小根笛卡尔树上钦定一个点作为最小值，然后问题变成从左子树和右子树各选一个点 a 和 b，使得 \sum\limits_{i=a}^bB_i\le S'。设在笛卡尔树上的 LCA 是 p，则套路地把和拆成 \sum\limits_{i=a}^pB_i+\sum\limits_{i=p+1}^jB_i，枚举一个端点以后也是类似上面那题的计数。

不能透露来源的题

给定一个长为 n 的序列，将这个序列划分成若干段，使得每一段的长度被夹在段内最小值和最大值之间，求方案数。1\le a_i\le n\le 5\times 10^5。

参考了一下这道题的题解区，表示感谢。

暴力 dp 不难想，f_i 代表前 i 个数划分成若干段的方案数，可以 O(n^2) 转移。将限制写出来是 \min\limits_{k=j+1}^i a_k\le i-j\le\max\limits_{k=j+1}^i a_k，发现前者的限制很好满足（等价于规定只能从一段前缀转移），后者的限制看上去很难直接做，考虑建立笛卡尔树进行最值分治，做中序遍历后钦定从左边转移到右边，按照上面启发式分治的套路做就好，如果用线段树维护的话是 2\log，但是整个过程中不会再变化的 dp 值永远是一段前缀，因此可以指针简单维护差分做到 O(n\log n)。