区间笛卡尔树

min_inf · 2025-11-12 21:30:33 · 算法·理论

考虑这样一类问题：有一个序列 a_{1\dots n}，每次询问一个区间建出来的笛卡尔树上的一些事情。

不妨假设 a_i 互不相同，我们需要的是大根笛卡尔树。考虑怎么刻画一个区间 [l,r] 的笛卡尔树：

• 首先根是区间最大值：p_0=\arg\max\limits_{i\in[l,r]}a_i。
• 考虑根的左子树 [l,p_0)，有左子树的根 p_1=\arg\max\limits_{i\in[l,p_0)}a_i。
• 我们可以发现 p_1 的右子树就是 p_1 在整个序列的笛卡尔树上的右子树；p_1 的左子树 p_2=\arg\max\limits_{i\in[l,p_1)}a_i，以此类推直到 p_k=l。
• 容易发现 p_k,p_{k-1},\dots,p_0 就是这个区间的所有前缀最大值的位置；根的左儿子就是这些前缀最大值（不包括 p_0）和它们在整个序列的笛卡尔树上的右儿子拼起来的结果。
• 维护的方式因题而异，一种常见的做法是从右到左扫描线，用一个递减的单调栈维护 [l,n] 的前缀最大值；p_1,\dots,p_k 就是单调栈的一个后缀，在单调栈上维护需要维护的信息。根的右儿子就是全部反过来，在最后拼出来根的信息。

::::info[QOJ14417. Roman Numerals] 题意：有序列 a_i,b_i，对区间 a_i 建出笛卡尔树，点 u 有 f_u=b_u-f_{ls_u}+f_{rs_u}，求根的答案。

首先我们对整个序列建出笛卡尔树并处理出 f_u。先考虑右儿子怎么做，可以发现就是单调栈上的一个后缀 b_u-f_{ls_u} 加起来，做一个前缀和就行。

左儿子也是类似，但是每个点的贡献要乘上 (-1)^{dep_u}。我们先将在单调栈上的位置的奇偶性当作深度的奇偶性，询问的时候分讨一下 p_0 位置的奇偶性。

通常为了方便，第一步的区间 RMQ 可以直接在单调栈上二分。本题使用线性 RMQ 即可做到线性，但通常没有什么必要。 ::::

::::info[P5044 [IOI 2018] 会议] 题意：有序列 a_i，每次询问 \min\limits_{i\in[l,r]}\sum\limits_{j\in[l,r]}\max\limits_{k\in[\min(i,j),\max(i,j)]}a_k。

我们先在笛卡尔树上写出 DP：f_u=\min(f_{ls_u}+a_u(sz_{rs_u}+1),f_{rs_u}+a_u(sz_{ls_u}+1))。

两边是对称的，我们就只考虑左边。我们考虑最小的 i 使得 p_i 采用了第二种转移，即 f_{p_i}=f_{rs}+a_{p_i}(p_i-l+1)，那 f_{p_1}=f_{p_i}+\sum\limits_{1\le j<i}a_{p_j}(sz_{rs_{p_j}}+1)，答案就是所有 p_i 的结果的最小值。在单调栈上前缀和然后拆贡献，KTT 维护一次函数最值。\mathcal O(n\log^2n)。 ::::

::::info[P13540 [IOI 2025] 羊驼的坎坷之旅] 题意：有一个网格，一个单元格 (x,y) 合法当且仅当 a_x>b_y，问保留第 [l,r] 列，(0,x) 能不能走到 (0,y)。

我们猜测路径一定形如一堆 (0,a)\to(x,a)\to(x,b)\to(0,b)。设一列中第一个空的位置是 fi_i，前缀连续空的长度是 cn_i，a\to b 之间的 \max b 位置为 c，那能这么走就相当于 fi_c\le\min(cn_a,cn_b)。

我们建出 b 的笛卡尔树。对于一个子树 x，如果我们能到达 fi_x 且子树 \max cn\ge fi_{fa_x} 就可以走到 fi_{fa_x}，询问的时候只要看能跳到最高的位置是否相等。

考虑区间笛卡尔树，所有前缀 \max 相当于不停跳到右侧第一个 >b_i 的位置，这个也能建出一棵树，在全局的笛卡尔树上倍增到子树不被 [l+1,r-1] 包含后变成在这棵树上倍增即可。O(n\log n)。 ::::