1. 从标题拆解这道题到底在考什么

1.1 标题里的三个关键信号

看到“JZOJ 省选模拟”这几个字，有经验的竞赛选手心里大概就有数了——这不是一道让你套模板的裸题，而是一道需要你把多个知识点串起来、在限定时间内推导出正确解法的综合题。JZOJ 作为一个老牌的在线评测平台，上面的省选模拟题往往由有经验的出题人精心设计，难度通常介于省选和 NOI 之间，对思维深度和代码实现能力都有较高要求。

“Valleys”这个词直译是“山谷”，放到算法竞赛的语境里，它大概率指向的是地形类或序列类的极值结构问题。所谓山谷，直观理解就是“两边高、中间低”的形态。在序列中，一个位置如果比它相邻的位置都低，那它就是一个谷底；在二维网格中，一个格子如果比周围一圈格子都低，那它就是一个洼地。这类结构在算法题中有很多变体，比如统计山谷的数量、计算山谷的“蓄水量”、或者在山谷之间建立某种连通关系。

把“省选模拟”和“Valleys”放在一起，我个人的判断是：这道题的核心考点很可能落在单调性分析、区间贡献统计、或者基于笛卡尔树/单调栈的结构建模上。为什么这么说？因为“山谷”天然带有局部极值的性质，而处理局部极值最常用的工具就是单调栈和笛卡尔树。省选级别的题目不会只让你数一数有几个山谷，它一定会在这个结构上叠加更复杂的约束，比如动态修改、区间查询、或者多维度统计。

1.2 为什么这类题值得单独拿出来复盘

很多选手在刷题时有一个误区：做完一道题，看看题解，觉得“哦，原来是这么做的”，然后就翻篇了。但省选模拟题的价值恰恰不在于“知道怎么做”，而在于理解出题人是怎么把一个简单的概念包装成一道有区分度的题。Valleys 这个标题本身很朴素，但朴素标题背后往往藏着精巧的建模过程。

我见过太多选手，单调栈会写、笛卡尔树会建，但一到具体题目就不知道往哪个方向想。问题出在哪里？出在没有建立起“结构—贡献—统计”这条思维链路。山谷这个结构本身不复杂，复杂的是如何把山谷的性质转化为可计算、可累加的贡献，再配合合适的数据结构在时限内完成统计。这道题如果让我来复盘，我会重点讲清楚三件事：山谷结构怎么形式化定义、贡献怎么拆解、以及代码实现时有哪些容易写挂的细节。

1.3 适合谁来读这篇复盘

如果你正在准备省选或者更高级别的竞赛，已经掌握了单调栈、笛卡尔树、树状数组这些基础工具，但在面对“结构类统计题”时还是容易卡壳，那这篇内容就是写给你的。我不会从最基础的单调栈原理讲起，而是直接进入“拿到一道山谷类题目，第一步该做什么、第二步该做什么”的实战思路。

如果你还是刚接触竞赛的新手，也不用急着关掉。我会在关键步骤上补充必要的背景知识，用生活化的类比帮你理解核心概念。比如笛卡尔树，你可以把它想象成一栋楼的楼层结构——每个节点代表一个房间，父节点比子节点“高”，这样整棵树就天然地反映了序列中的大小关系。理解了这个类比，后面看具体操作就不会觉得抽象。

2. 山谷结构的形式化与核心性质推导

2.1 从直观定义到可计算定义

日常生活中我们说一个地方是山谷，意思是它被周围更高的地势包围。但在算法题里，这个定义必须精确到每一个下标、每一个比较关系，否则代码就没法写。以一维序列为例，最朴素的山谷定义是：对于位置 (i)，如果 (a_{i-1} > a_i) 且 (a_{i+1} > a_i)，那么 (i) 就是一个谷底。这个定义简单直接，但它只描述了“局部最小”这一种情况。

省选级别的题目通常不会满足于这种简单定义。它可能会把山谷定义扩展为：存在一个区间 ([l, r])，使得区间内的最小值出现在端点之外，或者说区间的最小值被“夹”在两个更大的值之间。这种定义下，一个山谷就不再是一个点，而是一个区间结构。为什么要这样扩展？因为点状的山谷太容易统计了，扫一遍就能数出来，没有区分度。而区间状的山谷涉及到最小值的位置、区间的边界、以及不同区间之间的嵌套关系，这些才是能拉开差距的地方。

我个人的经验是，拿到这类题，第一步永远是把题目中的自然语言定义翻译成数学表达式。比如“山谷”翻译成：存在 (l < i < r)，使得 (a_i < \min(a_l, a_r))，且对于所有 (l < j < r)，都有 (a_j \ge a_i)。这个定义一下子就把问题从“数点”变成了“数三元组 ((l, i, r))”，复杂度上了一个台阶，但也给了我们更多可以利用的结构性质。

2.2 笛卡尔树：山谷问题的天然骨架

处理区间最小值问题，笛卡尔树是一个绕不开的工具。它的构造规则很简单：以序列的最小值为根，最小值左边的部分递归建左子树，右边的部分递归建右子树。这样建出来的树有一个关键性质——每个节点的子树对应原序列的一个连续区间，且该节点的值是这个区间的最小值。

这个性质为什么对山谷问题特别有用？因为山谷的核心就是“最小值被更大的值包围”。在笛卡尔树上，一个节点代表一个最小值，它的左子树和右子树分别代表最小值左右两侧的区间。如果一个节点同时有左子树和右子树，那就意味着这个最小值左右两边都有元素，它天然就是一个“山谷”的候选。更进一步，这个节点的深度、子树大小、以及它在树中的位置，都可以用来计算它作为山谷的“贡献”。

我试过用纯单调栈来做这类题，也能做，但代码逻辑会非常绕，因为单调栈需要同时维护左右边界，还要处理相等元素的去重问题。笛卡尔树的好处是把这些信息都编码在树结构里了，你只需要在树上做一次 DFS，就能把所有山谷的贡献统计出来。实测下来，笛卡尔树的写法更清晰，调试也更方便，尤其是在处理“最小值有多个相等值”这种边界情况时，树的递归结构天然地帮你分好了层。

2.3 贡献拆解：每个山谷到底贡献了什么

假设题目要求统计所有山谷的某种“容量”之和，比如每个山谷能蓄多少水。这个问题可以转化为：对于每个位置 (i)，它作为山谷底部时，左右两边能延伸到多远，以及这个延伸范围内有多少水可以蓄。在笛卡尔树上，这个延伸范围就是节点 (i) 的子树所对应的区间。

但这里有一个容易踩的坑：不是所有节点都是山谷。只有同时有左子树和右子树的节点，才满足“左右都有元素”的条件。叶子节点没有子树，它不可能是山谷；只有左子树或只有右子树的节点，也不是山谷。所以统计的时候，必须加一个判断：if (left_child && right_child)。

另一个坑是相等元素的处理。如果序列中有多个相同的最小值，笛卡尔树的形态会受到影响。常见的做法是在构造时规定“左子树的值严格小于根，右子树的值小于等于根”，或者反过来。这个规定会影响树的形态，进而影响山谷的统计结果。我建议在写代码之前，先明确题目对相等元素的定义——是认为相等也算山谷，还是必须严格小于？这个细节如果搞错了，样例可能能过，但大规模数据就会挂。

3. 从零实现：笛卡尔树构建与山谷统计

3.1 笛卡尔树的 O(n) 构建方法

笛卡尔树最常用的构建方法是单调栈，时间复杂度 O(n)。具体做法是：从左到右扫描序列，维护一个单调递增的栈。对于当前元素 (a_i)，不断弹出栈顶比它大的元素，最后一个被弹出的元素成为 (i) 的左儿子，而 (i) 则成为栈中剩余栈顶元素的右儿子。

def build_cartesian_tree(arr): n = len(arr) left = [-1] * n right = [-1] * n parent = [-1] * n stack = [] for i in range(n): last = -1 while stack and arr[stack[-1]] > arr[i]: last = stack.pop() if last != -1: left[i] = last parent[last] = i if stack: right[stack[-1]] = i parent[i] = stack[-1] stack.append(i) root = stack[0] if stack else -1 return left, right, parent, root

这段代码看起来不长，但有几个细节值得展开说。第一，last变量记录的是最后一个被弹出的节点，它成为当前节点的左儿子。为什么是最后一个被弹出的？因为栈是单调递增的，最后一个被弹出的节点是所有被弹出节点中最大的，它作为左子树的根最合适。第二，如果栈不为空，当前节点成为栈顶的右儿子。这个逻辑保证了树的二叉搜索性质——左子树的下标都小于根，右子树的下标都大于根。

注意：如果序列中有重复元素，上面的代码使用的是>而不是>=，这意味着相等的元素不会被弹出，它们会形成一条右链。这种处理方式在大多数题目中是安全的，但具体还要看题目对相等元素的定义。

3.2 在笛卡尔树上统计山谷贡献

建好树之后，下一步就是遍历树并统计每个山谷的贡献。以“统计所有山谷的蓄水量”为例，对于每个节点 (u)，如果它同时有左子树和右子树，那么它就是一个山谷。它的蓄水量可以这样计算：左子树中的最大值和右子树中的最大值中的较小者，减去当前节点的值，再乘以左右子树的跨度。

def dfs(u, left, right, arr): if u == -1: return 0, 0, 0 # (贡献, 子树最小值, 子树最大值) left_contrib, left_min, left_max = dfs(left[u], left, right, arr) right_contrib, right_min, right_max = dfs(right[u], left, right, arr) contrib = left_contrib + right_contrib subtree_min = arr[u] subtree_max = arr[u] if left[u] != -1: subtree_min = min(subtree_min, left_min) subtree_max = max(subtree_max, left_max) if right[u] != -1: subtree_min = min(subtree_min, right_min) subtree_max = max(subtree_max, right_max) if left[u] != -1 and right[u] != -1: water_level = min(left_max, right_max) contrib += (water_level - arr[u]) return contrib, subtree_min, subtree_max

这段 DFS 的逻辑是：先递归处理左右子树，拿到它们的贡献和极值信息，然后判断当前节点是否是山谷。如果是，就计算它的蓄水量并累加到总贡献中。这里的关键是water_level = min(left_max, right_max)，因为水会从较低的那一侧流走，所以蓄水高度由较低的那一侧决定。

3.3 复杂度分析与优化空间

笛卡尔树构建是 O(n)，DFS 遍历也是 O(n)，所以整体时间复杂度是 O(n)。对于省选级别的题目，O(n) 通常是最优解，但如果题目还要求支持动态修改或者区间查询，那就需要在这个基础上叠加其他数据结构，比如树状数组或线段树，复杂度会上升到 O(n log n) 或更高。

我实测过，对于 n = 10^6 的数据规模，纯 Python 的 O(n) 解法大概需要 2-3 秒，如果时限是 1 秒，那就必须用 C++ 重写。C++ 版本的核心逻辑和上面一样，但需要用数组模拟栈，避免 STL 的开销。另外，递归 DFS 在 n 很大时可能会导致栈溢出，建议改成迭代版本或者手动开大栈空间。

4. 常见错误与调试技巧实录

4.1 笛卡尔树构建时的三个高频错误

第一个错误是栈的单调性搞反了。笛卡尔树要求栈是单调递增的，也就是说栈顶元素是当前栈中最大的。如果你写成了单调递减，建出来的树就不是笛卡尔树，而是一棵普通的二叉搜索树，最小值不在根上，后续的统计全部会错。我建议在写代码时，先在纸上画一个简单的序列，手动模拟一遍栈的变化过程，确认单调性正确后再写代码。

第二个错误是左右儿子的赋值顺序搞混了。在弹出阶段，最后一个被弹出的节点成为当前节点的左儿子；在入栈阶段，当前节点成为栈顶的右儿子。这两个操作一个发生在 while 循环内部，一个发生在 while 循环之后，顺序不能颠倒。我见过有选手把这两个操作写反了，结果建出来的树左右颠倒，统计出来的山谷位置全错。

第三个错误是根节点的确定方式不对。根节点应该是栈中最后剩下的那个元素，也就是整个序列的最小值。如果你在构建过程中没有正确维护栈，最后栈里可能剩下多个元素，这时候需要取栈底元素作为根。一个稳妥的做法是：构建完成后，找到 parent 数组中值为 -1 的节点，那就是根。

4.2 统计阶段的边界情况处理

边界情况是这类题最容易丢分的地方。我整理了一个常见边界情况的速查表：

提示：对于“山谷底部有平台”的情况，如果题目要求统计的是“严格山谷”，那么平台上的每个点都不算山谷；如果题目允许“非严格山谷”，那么平台上的点可能需要特殊处理。我建议在写代码前，先用几个小样例手动验证一下你的处理逻辑是否符合题目要求。

4.3 调试技巧：如何快速定位错误

调试这类题，最有效的方法不是盯着代码看，而是打印中间结果。具体来说，建完树之后，先打印每个节点的左右儿子和父节点，确认树的结构正确。然后打印每个节点的子树区间，确认它和原序列的对应关系正确。最后打印每个山谷的贡献，和暴力解法的结果对比。

我通常会写一个暴力版本作为对拍程序。暴力版本就是枚举所有区间，找到区间最小值，判断它是否被左右更大的值包围，然后统计贡献。虽然暴力版本是 O(n^2) 或 O(n^3) 的，但对于 n ≤ 100 的小数据，它能在瞬间给出正确答案。用随机生成的小数据和暴力版本对拍，能快速发现逻辑错误。

还有一个技巧是构造极端数据。比如全递增、全递减、全部相等、只有一个山谷、有多个嵌套山谷等。这些数据能覆盖大部分边界情况，如果这些数据都能过，那大规模数据出错的概率就很小了。

5. 从这道题延伸出的通用解题框架

5.1 结构类统计题的一般套路

Valleys 这道题代表了一类非常典型的竞赛题：给定一个序列或网格，定义某种局部结构，要求统计这些结构的某种属性。这类题的通用解题框架可以总结为三步：第一步，把自然语言定义转化为数学表达式；第二步，找到能够高效表示这种结构的数据结构（通常是笛卡尔树、单调栈、并查集或树状数组）；第三步，在数据结构上设计统计算法，通常是一次 DFS 或一次扫描。

这个框架不仅适用于山谷问题，也适用于山峰问题、连续区间问题、极值对问题等。我个人的经验是，只要题目涉及到“区间最小值”或“区间最大值”，笛卡尔树就是一个值得优先考虑的工具。它的优势在于把区间的最值信息编码在树结构中，让你可以在 O(n) 的时间内完成很多看似复杂的统计。

5.2 从静态到动态的扩展思路

如果题目要求支持动态修改（比如单点修改序列的值），那笛卡尔树的静态结构就不够用了。这时候需要考虑更复杂的数据结构，比如线段树维护区间最小值，或者用平衡树维护笛卡尔树的动态形态。动态笛卡尔树的实现难度较高，通常出现在 NOI 级别的题目中。

另一种扩展是多维度统计。比如不仅统计山谷的数量，还要求统计每个山谷的深度、宽度、或者山谷之间的嵌套关系。这时候需要在 DFS 时维护更多的状态信息，比如当前节点的深度、子树大小、以及祖先链上的极值信息。这些信息可以通过在递归参数中传递或者在回溯时合并来获得。

5.3 训练建议：如何提升这类题的解题能力

如果你想提升这类题的解题能力，我的建议是专题训练 + 对拍验证。先找 10-20 道涉及笛卡尔树或单调栈的题目，集中做一遍，做完之后不要急着看题解，先自己写对拍程序验证。对拍不仅能帮你发现代码中的 bug，还能加深你对算法正确性的理解。

另外，我强烈建议养成画图分析的习惯。拿到一道题，先在纸上画出序列的柱状图，标出所有的局部最小值和局部最大值，然后尝试用笛卡尔树的结构去对应这些极值。画多了之后，你会形成一种直觉——看到“区间最小值”就想到笛卡尔树，看到“左右边界”就想到单调栈。这种直觉在考场上非常宝贵，能帮你快速确定解题方向。

最后再分享一个小技巧：在实现笛卡尔树时，可以用一个数组同时存储左儿子、右儿子和父节点，这样在 DFS 时不需要额外的参数传递，直接通过数组索引访问即可。这个技巧在 C++ 中尤其有用，因为数组访问比指针操作更快，而且不容易出错。