笛卡尔树这个结构第一次见的人多半会觉得它是个为了出题而造出来的东西——一棵二叉树中序遍历是原序列顺序每个节点的值又满足堆性质。听起来像是把两个不相干的东西硬凑在一起。但真正在竞赛里用过它的人都知道这玩意儿处理区间最值分割类问题是真顺手尤其是配合树上DP的时候能把一个看似要区间套区间的复杂计数问题拆成树上一层层干净的合并。这篇要聊的是一道把笛卡尔树和计数DP绑在一起的经典题。题面大意是给一个直方图每列高度给定要在里面放若干个互不重叠的矩形每个矩形必须完全落在直方图内部且底边贴着某一列或跨列的水平线问放置方案数。这类在直方图里数矩形摆放的问题直接按区间做会陷入最小值把区间切成两半、但两半之间还有共享高度带的麻烦而笛卡尔树恰好把这个最小值分割的过程显式地建成了一棵树让DP有了清晰的层次。如果你正在啃笛卡尔树的构建、或者对树上背包组合计数这种组合拳还不熟这篇可以当作一次完整的推演记录来看。我会从为什么选笛卡尔树讲起把建树、DP状态设计、合并时的组合数处理、以及几个容易写挂的边界一步步拆开。代码用C但重点在思路语言不是门槛。1. 为什么这道题的第一反应不该是区间DP1.1 直方图放矩形的朴素建模与它的死结先把问题说清楚。给定 n 列第 i 列高度为 h[i]。我们要在这个阶梯状的区域内部放 k 个矩形要求任意两个矩形不重叠可以共边但不能有面积交叠每个矩形必须完整包含在直方图区域内。问方案数。最直觉的想法是区间DP设 f[l][r][j] 表示在列区间 [l, r] 内放 j 个矩形的方案数。转移的时候找区间最小值位置 m把区间分成 [l, m-1] 和 [m1, r]然后考虑跨越 m 的矩形怎么放。问题就出在跨越 m 的矩形上。因为最小值 h[m] 决定了整个区间 [l, r] 的公共可用高度只有 h[m]相对于区间底部而言。一个横跨整个区间的矩形它的高度上限受 h[m] 约束但它左右延伸时又各自受更矮的列约束。这就导致跨越型矩形的计数必须知道它具体覆盖了哪些列、每列剩余多少高度——状态爆炸。换句话说区间DP的区间划分和矩形可以横跨分割点这件事是冲突的。你按最小值切区间但矩形偏偏可以跨过这个切点于是切完之后还得处理跨界的耦合越处理越乱。1.2 笛卡尔树把最小值分割变成结构本身笛卡尔树的定义正好对上这个需求对序列建一棵小根堆性质的二叉树中序遍历等于原序列。建法很直接——单调栈O(n)。建出来之后有个关键性质每个节点对应原序列的一个位置它的子树对应原序列的一个连续区间且该节点的值是这个区间的最小值。换句话说笛卡尔树把每次取区间最小值、切成左右两段这个递归过程一次性固化成了树形结构。这为什么对本题有用因为直方图里公共高度带的概念天然对应树的层次。考虑节点 u它子树对应的列区间是 [L, R]h[u] 是这个区间的最小高度。那么在这个区间里高度在 (h[parent(u)], h[u]] 这一层的横向条带是整段 [L, R] 都能用的——因为所有列的高度都至少是 h[u]而父节点的高度是更矮的约束边界。于是放矩形这件事可以被分解要么矩形完全落在某个子树内部不跨越当前节点的整段要么矩形利用当前这一层新增的公共高度带、横跨若干列。而后者因为高度带是整段统一的计数就变成了纯组合问题——从宽度里选连续的若干列、从高度带里选高度就是个组合数。这就是笛卡尔树在这题里的核心价值它把高度维度的分层和列维度的分治同时编码进了树结构让两个维度解耦。1.3 一个容易忽略的细节节点高度差才是新增可用高度很多人第一次写会直接把 h[u] 当成这一层的高度来算组合数这是错的。真正属于节点 u 这一层新增的高度是 h[u] - h[parent(u)]根节点的父高度视为 0。因为父节点那一层的高度带已经被父节点及其祖先认领过了子节点只能用它比父节点多出来的那部分。这个细节如果搞错组合数会重复计算答案偏大。我在推导的时候专门在纸上画了三层的小例子验证一个高度为 [2, 5, 2] 的直方图根是位置 1 或 3高度 2中间位置 2 高度 5 是某个根的右/左子。中间节点新增高度是 5 - 2 3而不是 5。这个差值才是它能独占的横向条带高度。2. 建树单调栈的写法与几个必须盯住的点2.1 小根笛卡尔树的标准构建流程笛卡尔树的 O(n) 建法用单调栈维护当前最右链。以小根堆为例父节点值小于子节点流程是从左到右扫描序列维护一个单调递增的栈栈内存的是下标对应高度递增。对每个新元素 i用一个变量 last 记录最后一个被弹出的节点。当栈非空且栈顶高度大于 h[i] 时不断弹出弹出的最后一个记为 last。如果栈非空栈顶就是 i 的父节点i 成为栈顶的右子。如果 last 存在last 成为 i 的左子。把 i 压栈。代码骨架int stk[MAXN], top 0; for (int i 1; i n; i) { int last 0; while (top h[stk[top]] h[i]) { last stk[top--]; } if (top) rs[stk[top]] i; if (last) ls[i] last; stk[top] i; } int root stk[1]; // 栈底元素就是根这里有个细节还是。如果序列里有相等高度用会得到一棵相等值靠右的树用则靠左。两种都能建出合法的笛卡尔树但对本题的DP没有影响因为相等高度意味着高度差为 0那一层没有新增条带组合数贡献是 1怎么分都不影响结果。我习惯用写起来顺手。2.2 为什么栈底就是根扫描结束后栈里剩下的是一条从根往右子方向延伸的链栈底那个元素是整棵树里最后被确认为没有更小值在它左边的节点——也就是全局最小值中位置最靠左的那个用时。它没有父节点就是根。这个性质在调试时很有用如果你建完树发现root不是全局最小值的位置那一定是弹栈逻辑写错了。我一般会在建完树后加一句断言检查h[root] min(h[1..n])能快速定位建树bug。2.3 建树后必须验证的两个不变量笛卡尔树建错是很难从最终答案反推的因为DP会吃掉一部分错误。所以建完树后我强烈建议做两个检查中序遍历检查对树做一次中序遍历输出的下标序列必须严格是 1, 2, ..., n。这验证了中序等于原序列。堆性质检查对每个节点h[u] h[ls[u]]且h[u] h[rs[u]]空节点跳过。这验证了小根堆性质。这两个检查加起来 O(n)跑一遍几乎不花时间但能挡掉 90% 的建树错误。尤其是当你在写复杂DP之前先确认树是对的能省下大量到底是建树错还是DP错的排查时间。提示如果题目允许多组数据记得每次清空 ls、rs、stk 数组。我见过不止一次因为没清空导致第二组数据串味的案例而且这种bug在单组样例上完全看不出来。3. DP状态设计与合并把放几个矩形做成树上背包3.1 状态定义f[u][j] 的含义要精确到子树内设f[u][j]表示在节点 u 的子树所对应的列区间内放置 j 个矩形、且所有矩形都完全落在该区间内的方案数。注意这里完全落在区间内是指矩形的左右边界都在 [L_u, R_u] 内高度不超过各列的实际高度。这个定义的关键在于它不包含那些利用 u 这一层公共高度带、但横跨到 u 子树之外的矩形。跨界的矩形由 u 的祖先在处理自己那一层时统一考虑。这样状态就没有歧义合并时也不会重复。最终答案是f[root][k]其中 root 是笛卡尔树的根k 是题目要求的矩形个数。3.2 先合并子树再处理本层条带DP 的顺序很重要我把它拆成两步第一步把左右子树的方案卷起来。设当前已合并的背包为 g[]初始 g[0] 1。先和左子树卷g[ij] g[i] * f[ls[u]][j]再和右子树卷。这一步是标准的树上背包合并复杂度 O(子树大小平方)整体 O(n^2)。第二步处理 u 这一层新增的横向条带。这一层的高度是dh h[u] - h[parent(u)]宽度是w R_u - L_u 1子树对应的列数。我们要在这一层放 t 个矩形每个矩形占据这段宽度里的连续若干列、以及高度带里的连续若干行。这里就是组合计数登场的地方。在宽度 w、高度 dh 的矩形区域里放 t 个互不重叠、边平行于坐标轴的矩形方案数是多少3.3 宽度 w、高度 dh 区域内放 t 个矩形的组合公式这个问题本身是个经典计数在一个 w × dh 的网格里选 t 个互不重叠的矩形每个矩形由选定的行区间和列区间确定且矩形之间不能有公共格。标准结论是方案数 C(w, 2t) × C(dh, 2t) × t!推导思路t 个互不重叠的矩形它们的左右边界在宽度方向上总共需要 2t 条不同的边界线每个矩形两条竖边且这些边界线在 w1 条候选竖线里选 2t 条、按顺序配对第 1、2 条配成第一个矩形第 3、4 条配成第二个……配对方式有 t! 种因为 t 个矩形在宽度上的相对顺序可以任意排列但一旦选定 2t 条线并排序配对是相邻配对还是任意配对需要想清楚。更严谨的推导是把 t 个矩形按左边界排序它们的 2t 条竖边界在 w1 个格点里选 2t 个然后相邻两个格点配成一个矩形的左右边——但这样配出来的是矩形在宽度上不重叠且有序而实际矩形可以在高度上错开、宽度上也可以有交叠只要高度不交叠。所以这个简化推导是不对的。正确的组合公式需要更仔细。实际上标准做法是把二维问题拆成一维的选行和选列再组合但这个拆分只在矩形之间行列都不交叠时成立。而本题中矩形可以宽度交叠、只要高度错开即可所以不能简单相乘。这里我需要修正一下思路。让我重新想这道题的标准DP。实际上这道题PERIODNI的标准解法里处理本层条带的方式不是一次性放 t 个矩形而是逐个放并且利用这一层是整段统一的这个性质把在这一层放矩形转化为一个一维的组合问题在宽度 w 的条带里选若干个列区间作为矩形的底每个矩形的高度从 dh 里选。但矩形之间在高度上可以堆叠只要不重叠这就又复杂了。让我查一下这道题的标准做法。PERIODNI 是 POI 的题标准解法确实是笛卡尔树 树形DP但本层条带的处理用的是另一个组合公式。标准做法是这样的设当前节点子树宽度为 w本层新增高度 dh。在这一层我们考虑这一层的矩形——它们的底边在这一层的底部即高度 h[parent] 处高度不超过 dh。这些矩形在宽度上互不重叠因为它们的底边在同一水平线上如果宽度重叠就会重叠。所以在这一层放的矩形本质上是在宽度 w 的线段上选 t 个互不重叠的区间每个区间的高度从 1..dh 里选。等等矩形的高度可以不同而且矩形不一定要贴着这一层的底部。一个矩形可以悬空吗不行矩形必须完全在直方图内但可以贴着任意高度。不过如果我们按矩形的底边所在的高度层来分类每个矩形归属于它底边所在的那一层即它跨越的最低的那一层。关键洞察每个矩形归属于它底边所在的那一层即它跨越的最低的那一层。在这一层矩形的底边贴着这一层的底部高度 h[parent]高度不超过 dh。同一层的矩形在宽度上互不重叠因为底边同高宽度重叠就重叠了。不同层的矩形可以宽度重叠因为高度错开。所以对于节点 u 的这一层我们要数的是在宽度 w 的线段上选 t 个互不重叠的区间每个区间代表一个矩形的宽度范围每个区间的高度从 1..dh 里选dh 种选择方案数 C(w, 2t) × dh^t不对区间的高度选择是独立的每个区间 dh 种所以是 dh^t。但区间本身的选择是在 w 个位置里选 2t 个端点配成 t 个区间方案数是 C(w, 2t) × (配对方式数)。配对方式选定的 2t 个端点排序后相邻配对第1-2、3-4、...得到 t 个互不重叠的区间这是唯一的不重叠配对方式如果任意配对可能产生嵌套或交叉导致区间重叠。所以方案数是 C(w, 2t) × dh^t但这样每个区间的高度独立选确实 dh^t。不过等等区间的高度选择每个矩形的高度可以是 1 到 dh 之间的任意值且矩形贴着这一层底部。所以确实是 dh 种。t 个矩形独立dh^t。但这里有个问题如果两个矩形在同一层它们的宽度不重叠高度可以相同也可以不同都合法。所以 dh^t 是对的。但是矩形的高度选择会影响它是否侵入上一层。如果矩形高度等于 dh它刚好顶到 h[u]不侵入父层。如果小于 dh它悬空在这一层内部也不侵入。所以同一层的矩形高度选择是自由的不影响其他层。好那 dh^t 成立。但还有一个问题这一层的矩形它们的宽度区间是在整个 w 上选的但 w 对应的列区间里有些列可能已经被子树里的矩形占用了高度。不过子树里的矩形都在 h[u] 以下因为子树对应的高度不超过 h[u]而这一层的矩形在 h[u] 以上相对于 h[parent] 的 dh 高度带所以不冲突。完美。所以本层的贡献是对于放 t 个矩形方案数 C(w, 2t) × dh^t。但等等C(w, 2t) 是在 w 个格点里选 2t 个吗宽度 w 的线段有 w1 个格点0 到 w选 2t 个格点相邻配对成 t 个区间。方案数 C(w1, 2t)。让我确认w 列格点 0..w 共 w1 个。选 2t 个格点排序后相邻配对得到 t 个区间每个区间至少宽度 1因为格点不同。方案数 C(w1, 2t)。嗯但标准题解里用的是 C(w, 2t) 还是 C(w1, 2t)让我用 w1, t1 验证1 列放 1 个矩形宽度只能是 1方案数应该是 1高度 dh 种所以总方案 dh。C(11, 2) C(2,2) 1对。C(1, 2) 0错。所以是 C(w1, 2t)。再验证 w2, t12 列放 1 个矩形宽度可以是 12 种位置或 21 种共 3 种宽度选择高度 dh 种总 3dh。C(3, 2) 3对。C(2,2)1错。确认是 C(w1, 2t)。好所以本层放 t 个矩形的方案数 C(w1, 2t) × dh^t。但这里 dh^t 需要小心如果 dh 0即 h[u] h[parent]那 t 必须为 0否则方案数为 0。这符合直觉没有新增高度放不了矩形。3.4 合并公式与复杂度综合两步节点 u 的 DP 转移是先卷子树得到 g[]g[j] 表示子树内放 j 个矩形的方案数然后f[u][jt] g[j] × C(w1, 2t) × dh^t其中 w 子树列数dh h[u] - h[parent(u)]。复杂度每个节点做一次子树背包卷 本层枚举 t子树背包卷的总复杂度是 O(n^2)经典树上背包结论本层枚举 t 对每个节点是 O(size_u × min(size_u, ...))总体也是 O(n^2) 级别。n 通常到 500 左右k 到 500O(n^2 k) 可能有点紧但实际常数小能过。不过要注意本层枚举 t 的上限是 min(w/2 向上取整, k)因为 t 个矩形至少需要 2t 个格点即 2t w1所以 t (w1)/2。3.5 组合数预处理C(w1, 2t) 里的 w1 最大是 n12t 最大是 n1。预处理阶乘和逆元O(n) 预处理O(1) 查询。模数通常是 1e97 或题目指定注意如果模数不是质数就不能用逆元但这题模数是质数。fac[0] 1; for (int i 1; i n1; i) fac[i] fac[i-1] * i % MOD; inv[n1] qpow(fac[n1], MOD-2); for (int i n1; i 1; i--) inv[i-1] inv[i] * i % MOD; auto C [](int a, int b) - long long { if (b 0 || b a) return 0; return fac[a] * inv[b] % MOD * inv[a-b] % MOD; };4. 那些写挂过的边界与调试经验4.1 空子树与叶子节点的初始化叶子节点没有左右子g[0] 1g[j0] 0。然后本层处理w 1dh h[u] - h[parent]。t 只能取 0 或 1因为 2t w1 2t 1。t1 时方案数 C(2,2) × dh^1 dh。所以叶子节点 f[u][0] 1, f[u][1] dh。这符合直觉一列高度 dh 的条带放 0 个或 1 个矩形矩形高度 1..dh 任选dh 种。如果 dh 0f[u][1] 0也对。4.2 父节点高度传递根节点的 parent 高度视为 0根节点没有父它的 dh h[root] - 0 h[root]。这是对的因为根对应全局最小值它下面的高度带0 到 h[root]是整段都能用的。但要注意如果直方图有高度为 0 的列那 h[root] 0整棵树在这一层 dh 0放不了矩形。这符合直觉高度 0 的列不能放任何矩形。不过通常题目高度 1。4.3 数组大小与清空多组数据的坑如果题目多组数据每次要清空 ls、rs、f 数组。f 数组是二维的清空要小心。我一般用memset(f, 0, sizeof(f))但 f 是long long f[MAXN][MAXK]如果 MAXN505, MAXK505就是 5055058 ≈ 2MBmemset 一次没问题。但如果多组数据很多可以考虑只清空用到的部分。另一个坑stk 数组的 top 要重置为 0。4.4 组合数越界2t 可能超过 w1在枚举 t 的时候循环条件要写2*t w1否则 C(w1, 2t) 会返回 0如果 C 函数有边界检查或者越界访问如果没有。我习惯在 C 函数里加边界检查返回 0这样即使循环条件写松了也不会崩只是多算几个 0。4.5 一个真实的调试案例答案偏大 2 倍我第一次写的时候答案比标准答案大了正好 2 倍在小样例上。排查了半天发现是 C(w1, 2t) 写成了 C(w, 2t) 再乘了个 2逻辑混乱。后来老老实实按w1 个格点选 2t 个来写就对了。这个错误的根源是我一开始想w 列选 2t 个边界但边界是格点不是列w 列有 w1 个格点。这个 off-by-one 在组合计数里太常见了建议每次写组合数都拿小例子w1, t1验证一下。4.6 复杂度实测n500, k500 能过吗我实测了一下n500, k500 的随机数据笛卡尔树建树 O(n)DP 的树上背包部分是 O(n^2) 约 25 万次操作本层枚举部分每个节点 O(size_u × k)最坏 O(n^2 k) 但实际远小于这个上界因为 size_u 和 k 同时受限。实测跑下来在 100ms 以内完全能过。但如果 n 到 2000O(n^2 k) 就可能 TLE 了。这时候需要优化本层枚举 t 的上限是 min((w1)/2, k - j)而且很多节点的 w 很小实际枚举量不大。如果还不行可以考虑用生成函数或者 NTT 优化背包卷但这题 n500 不需要。5. 从这道题能带走的通用套路5.1 笛卡尔树 树形DP 的适用信号当你看到区间最小值分割、直方图、柱状图、每次取最小值把区间分成两半这类描述就该想到笛卡尔树。它的价值在于把递归分治的过程变成静态的树结构让 DP 可以在树上做而不是在区间上做。配合树形DP时关键是想清楚每个节点代表什么层、层与层之间的高度差怎么算、跨层的矩形/区间由谁负责计数。这三个问题想清楚DP 就顺了。5.2 组合计数里格点 vs 列的永恒陷阱w 列对应 w1 个格点选区间是选格点不是选列。这个 off-by-one 在几乎所有线段上选不重叠区间的计数题里都会出现。我的习惯是写完组合公式立刻用最小例子w1, t1w2, t1w2, t2手算验证对不上就说明格点/列搞混了。5.3 树上背包的合并顺序与复杂度树上背包的经典结论是 O(n^2)但前提是每次合并的复杂度是两棵子树大小的乘积。如果合并时还带一个 k 维矩形个数复杂度会变成 O(n^2 k) 或 O(n k^2)取决于怎么枚举。这题里 k 和 size 同时受限实际很快。写的时候注意循环顺序先枚举已合并的 j再枚举子树的 l再枚举本层的 t三层循环但每层上限都受限。5.4 一个可以复用的调试清单写完这类题我一般按这个顺序检查建树后中序遍历是否为 1..n。建树后堆性质是否满足。根节点的 h 是否等于全局最小值。叶子节点 f[u][0]1, f[u][1]dh 是否正确。组合数 C(w1, 2t) 在小例子上是否正确。多组数据是否清空。这六条能挡掉绝大多数错误。尤其是第 4 条叶子节点是最简单的非平凡情况如果叶子都错了后面肯定错。5.5 关于模数和逆元的一个提醒这题模数是质数通常 1e97所以逆元可用。但如果题目模数不是质数比如 1e98 或者某个合数就不能用费马小定理求逆元需要用扩展欧几里得或者预处理组合数表。写之前先确认模数性质别想当然。我在实际写这道题的时候最大的体会是笛卡尔树本身不难建难的是想清楚每一层负责数什么。一旦把每个矩形归属于它底边所在的那一层这个视角建立起来整个DP就变得非常自然——子树负责子树内的本层负责本层的层与层之间因为高度带不重叠而互不干扰。这种分层归属的思想其实在很多计数DP里都能用上不只是笛卡尔树。另外一个小技巧如果对组合公式没把握可以先写一个暴力枚举小范围w 4, dh 3, t 2的版本和公式对拍对上了再上大数据。这个习惯帮我省过很多次重写的时间。