P1950 这道题第一次见的人十有八九会被那个“神秘公式”劝退但如果你把这题吃透你对单调栈的理解会直接上一个台阶。我花了三个晚上才完全搞明白那个乘法公式为什么能不重不漏地数出所有合法矩形期间反复 WA、反复对着样例手算最后才把边界处理和单调栈的写法彻底理顺。这篇就把完整思路、公式推导和踩坑过程一次讲清楚。1. 先搞清楚题目在数什么题意拆解与样例验证1.1 “合法矩形”的真实定义题目背景通常是一个 n 行 m 列的网格每个格子上有字符一般是*表示障碍.表示可通行。你需要求的是所有完全由.组成的矩形子网格的个数。这里“矩形”不要求是正方形也不要求是最大的任何一个 1×1、1×2、2×3、甚至整个网格本身只要内部不包含任何*都算一个合法矩形。注意两个矩形只要占据的格子范围有一点点不同就算两个不同的矩形即使它们面积一样。这也是这题和“最大矩形面积”类题目的本质区别最大矩形只要找出一个这题要把所有可能的情况全部数出来。1.2 手算小数据先建立直观感受先拿一个最简单的 2×2 全.网格来手算.. ..逐个枚举全部子矩形1×14 个每个格子单独1×2 横条第1行 1 个第2行 1 个共 2 个2×1 竖条第1列 1 个第2列 1 个共 2 个2×2 整体1 个总数是 4 2 2 1 9 个。这个 9 不是随便来的。对于一个全.的 n×m 网格合法矩形数有闭式公式n(n1)/2 × m(m1)/2。2×2 代进去是 3×39正好吻合。这个公式你也可以这样理解一个矩形由“上边界、下边界、左边界、右边界”四个边界决定上下边界各选一对有 n(n1)/2 种左右边界同理一共就是乘积。所以这题的基准校验目标很明确全.数据下答案必须等于这个值。1.3 暴力枚举为什么救不了复杂度账本最直接的思路枚举矩形的上下边界、左右边界再用前缀和判断里面有没有障碍。枚举上边界 n 种、下边界 n 种、左边界 m 种、右边界 m 种组合起来是 O(n²m²)。判断区间是否合法可以 O(1) 用二维前缀和完成但枚举本身已经爆炸。当 n、m 都到 1000 甚至 2000 时n²m² 就是 10^12 到 10^14 级别完全不可行。这也是这个题最核心的难点不是判断合法难而是计数的效率难。所有高级做法都在回答同一个问题——如何把枚举复杂度从 n²m² 降到 nm 级别。2. 把二维压成一维悬线直方图视角的转换2.1 固定底边h[i][j] 的物理意义二维问题压成一维最经典的手段是把每一行当作“底边”向上看连续的.有多高。定义状态 h[i][j]第 i 行第 j 列这个格子上方连续有多少个.包含自身。递推式是如果格子 (i,j) 是*h[i][j] 0否则 h[i][j] h[i-1][j] 1。这个 h 数组有什么用想象把第 i 行当作地面每个柱子 j 的高度就是 h[i][j]那么这一行就变成了一个不规则的直方图。直方图里每个宽度为 1 的柱子它的高度代表从这个底边出发向上能延伸的连续.的层数。关键结论以第 i 行为底边的所有合法矩形恰好对应这个直方图里所有“高度连续≥1 的矩形子区间”。你只需要累计每一行作为底边时的合法矩形数就是整个网格的答案。因为任意一个合法矩形恰好有一个唯一确定的底边它占据的最下面一行不会重复也不会遗漏。把 n 行各自当作底边分别计算总复杂度是 O(n × 处理一行直方图的复杂度)。如果每行直方图能 O(m) 搞定整体就是 O(nm)。2.2 直方图里的矩形怎么数从“柱子”切换到“区间”现在问题从二维降到一维给你一串柱子高度 h[1..m]求这个直方图里有多少个子矩形宽度任意从底边往上延伸高度不能超过区间内最矮的柱子。这里有个角度转换非常关键不要按区间去枚举而是按柱子去计数。每个矩形区间 [L, R]它的高度上限由区间内最低的柱子 hmin 决定因此高度可以是 1 到 hmin 的任意值贡献是 hmin。如果我还是按区间枚举复杂度还是 O(m²)。但换个思路对于每个柱子 j能不能找到以它作为“最低柱子代表”的那些矩形然后用公式直接算出它代表多少个矩形这就要引出一个著名的计数技巧——每个矩形让它和区间内某个特定的最低柱子绑定这样每个矩形只被一个柱子“认领”一次不重不漏。2.3 单调栈的引入寻找左右最近的更矮柱子要让柱子 j 作为“最低代表”需要确定 j 能管辖的区间范围左边找第一个高度严格小于h[j] 的柱子位置 L右边找第一个高度小于等于h[j] 的柱子位置 R。L 和 R 是开边界也就是说 j 能代表的区间是 (L, R) 这个开区间内的任意子区间且这个子区间必须包含 j。为什么找第一个更矮的柱子因为一旦区间扩到包含一个比 h[j] 更矮的柱子最低柱子就不再是 j 了这个矩形应该由那个更矮的柱子认领。找到两边最近的更矮柱子就锁定了 j 作为最低柱子时能向外扩展的最大范围。“严格小于”和“小于等于”为什么要一高一低这是为了处理高度相等的柱子。如果两边都用严格小于等于高度的柱子区域会出现重叠导致某些矩形同时被两个相等的柱子认领重复计数如果两边都用小于等于又可能出现某些矩形没有任何柱子认领通常出现在完全平的区域里。一严格、一非严格恰好把相同高度的柱子按从左到右的顺序“划分地盘”每个矩形一定被其中某一个认领且仅被一个认领。寻找左右最近更矮柱子这件事正是单调栈最经典的应用场景。从左到右维护一个高度严格递增的栈每个元素出栈时就能确定它右边最近的更矮/更矮等于位置反过来从右往左扫一遍能确定左边最近的严格更矮位置。两趟 O(m) 扫描所有 L[j] 和 R[j] 就都拿到了。3. “神秘公式”深挖h[j] × (j−L) × (R−j) 为什么对3.1 组合数视角为什么是三个数相乘拿到 L[j] 和 R[j] 以后柱子 j 认领的合法矩形来自左边界选在 (L, j] 之间的任意一列右边界选在 [j, R) 之间的任意一列高度选 1 到 h[j] 之间的任意整数。这三个自由度完全独立左边界可能的位置数 j − L右边界可能的位置数 R − j高度可能的选择数 h[j]。所以柱子 j 的贡献是贡献 h[j] × (j − L[j]) × (R[j] − j)这个乘法结构本质上是在做组合计数左边界、右边界、高度每个维度各选一个三个选择拼起来恰好确定唯一的一个矩形。这就是所谓“神秘公式”的庐山真面目它一点都不神秘其实就是分步乘法计数原理。3.2 不重不漏的关键让“最低柱子”当唯一代表严谨地说这个公式能成立必须证明两件事第一不漏。任意一个合法矩形设其区间为 [a, b]高度为 h。取这个区间内最靠右的最低柱子或最靠左的取决于你的边界约定。这个柱子 j 满足 h[j] h并且向左没有更矮柱子挡住向右也没有更矮柱子挡住。也就是说 a 在 (L[j], j] 内b 在 [j, R[j]) 内于是这个矩形完全落在 j 的管辖范围内会被 j 的公式老老实实数到。第二不重。一个矩形会不会同时被两个不同柱子认领假设它同时被 j 和 k 认领j k那么 j 和 k 的高度都等于该矩形的高度 h。由于它们都选到了同一个区间 [a, b]且这个区间整体高度为 h说明区间内所有柱子高度 ≥ h。但 j 和 k 的高度都等于 h说明在区间内存在两个相等的“最低”。如果边界约定是左边严格更矮、右边非严格更矮那么从 j 的角度看k 在 j 的右边且高度等于 hj 的右边界 R[j] 就会在 k 的位置处截止因为“小于等于”k 就不在 j 的管辖范围内。反过来 k 的左边遇到 j 时因为要求“严格小于”j 的高度等于 h 并不会挡住 k所以 k 可以继续向左覆盖到包含 [a, b]。最终计数任务被唯一地分配给了“区间内最靠右的那个最低柱子”。这不重不漏的证明本质上就是等号分配规则在起作用。3.3 手动模拟一行数据验证公式拿一行高度数据[1, 2, 1]来手算验证公式是否等于穷举结果。逐个数一共有多少个合法矩形全部子区间是 [1,1]、[2,2]、[3,3]、[1,2]、[2,3]、[1,3]对应高度贡献分别是 1、2、1、1、1、1总和是 7。现在用单调栈法j1h1。左边没有更矮L0右边第一个小于等于 1 的是 j3R3。贡献 1 × (1−0) × (3−1) 2。j2h2。左边第一个严格小于 2 的是 j1L1右边第一个小于等于 2 的是 j3R3。贡献 2 × (2−1) × (3−2) 2。j3h1。左边第一个严格小于 1 不存在L0右边不存在R4。贡献 1 × (3−0) × (4−3) 3。总数 2237与穷举一致。再看一个高度相等的例子[2, 2, 2]j1L0右边第一个小于等于 2 的是 j2R2。贡献 2 × 1 × 1 2。j2L0左边严格小于 2 不存在右边 j3 高度等于 2所以 R3。贡献 2 × 2 × 1 4。j3L0R4。贡献 2 × 3 × 1 6。总数 12。而全 2×3 的矩形总数应该是 n2、m3 代入 3×618等等这里只有一行高度 2 的直方图矩形可以从 1 到 2 层高所以宽度为 1 的区间3个各贡献 2宽度为2的区间2个各贡献 2宽度为3的区间1个贡献 2合计 (321)×212。公式结果正确。这个手算过程强烈建议你自己也推一遍。你能亲手验证出“神秘公式”和穷举结果每次都对得上你才算真正信了这个做法。4. 代码落地与边界情况从思路到 AC 的完整实现4.1 高度数组的预处理细节读入网格的时候可以一边读一边算 h不需要单独存整个网格。按行读取字符串对每个字符判断如果是*h[j] 0如果是.h[j] 上一次的这个值 1。注意数组 h 是逐行更新的这一行算完就用这一行的 h 值去跑单调栈跑完再读下一行空间复杂度只有 O(m)非常省。int h[MAXM]; for (int i 1; i n; i) { string s; cin s; for (int j 1; j m; j) { if (s[j-1] *) h[j] 0; else h[j]; } // 用当前的 h[] 跑单调栈统计这一行 }这里有个细节h[j]确实是随着行号增加而增加的但如果中间遇到障碍物被清零再遇到.就从头开始完全符合“连续向上”的定义。4.2 两趟扫描法与一趟扫描法的选择理论上可以只从左往右扫一遍利用弹栈的时机同时确定右边界再在后续补算左边界。但那种写法对新手来说太容易绕晕。我建议老老实实写两趟第一趟从左往右维护单调递增栈求每个位置右边第一个小于等于它的位置 R[j]第二趟从右往左维护求每个位置左边第一个严格小于它的位置 L[j]。// 求 R[]右边第一个 h[R[j]] h[j] 的位置没有则 m1 int top 0; for (int j 1; j m; j) { while (top 0 h[st[top]] h[j]) { R[st[top]] j; top--; } st[top] j; } while (top 0) R[st[top--]] m 1; // 求 L[]左边第一个 h[L[j]] h[j] 的位置没有则 0 top 0; for (int j m; j 1; j--) { while (top 0 h[st[top]] h[j]) { // 注意这里要 因为左侧要求严格小于 // 严格小于的意思是遇到相等不算更矮 top--; } L[j] (top 0 ? 0 : st[top]); st[top] j; }注意两个循环里h[st[top]] h[j]的等号处理是故意不对称的求 R 时用弹出所有高度大于等于当前的所以右边第一个留下的位置高度是“严格小于”的但题目要求右边的边界是“小于等于”截止。等等这里要仔细想清楚。其实很多题解的写法是求右侧时弹出然后“当前 j 就是被弹出位置的右边界”。被弹出的位置高度 h[old] ≥ h[j]也就是说 j 是 old 右边第一个高度小于等于h[old] 的位置所以 R[old] j。这个理解是对的。在代码里你是用被弹出的元素记录边界而不是用栈顶。求左侧同理从右往左扫弹出当前 j 就是被弹出位置的左边界因为左侧要求“严格小于”所以 h[j] ≥ h[old] 时应该弹出并记录 L[old] j。只有当 j 的高度严格小于h[old] 时j 才是 old 左边第一个更矮的位置才作为 L[old] 保留。所以左右边界不对称的真正原因是右边要找“小于等于”的截止点左边要找“严格小于”的截止点。代码里弹出的条件都是但记录的边界含义不同一个是 R一个是 L。为了避免混淆我建议把左右两趟分开写并在注释里写清楚当前记录的是哪个边界。4.3 完整参考代码与一行模拟#include bits/stdc.h using namespace std; const int MAXM 1005; int h[MAXM], L[MAXM], R[MAXM], st[MAXM]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin n m; long long ans 0; for (int i 1; i n; i) { string s; cin s; for (int j 1; j m; j) { if (s[j - 1] *) h[j] 0; else h[j]; } int top 0; for (int j 1; j m; j) { while (top 0 h[st[top]] h[j]) { R[st[top]] j; top--; } st[top] j; } while (top 0) R[st[top--]] m 1; top 0; for (int j m; j 1; j--) { while (top 0 h[st[top]] h[j]) { L[st[top]] j; top--; } st[top] j; } while (top 0) L[st[top--]] 0; for (int j 1; j m; j) { if (h[j] 0) continue; // 障碍柱不产生任何矩形 ans 1LL * h[j] * (j - L[j]) * (R[j] - j); } } cout ans \n; return 0; }跑一行[1,2,1]的过程求 R从左往右压栈。j1 入栈j2 高度2栈顶1的 h1 2不弹j2 入栈j3 高度1先弹 j2 记 R[2]3再弹 j1 记 R[1]3然后 j3 入栈结束后栈里剩 j3记 R[3]4。求 L从右往左压栈。j3 入栈j2 高度2栈顶3的 h1 2不弹L[2]3j1 高度1开始弹栈顶 j2 的 h2 ≥ 1弹掉记 L[2]1等等这里顺序要理清被弹出的栈顶元素记录 L 值为当前 j。弹掉 j2 记 L[2]1再弹 j3 记 L[3]1然后 j1 入栈结束后栈里剩 j1记 L[1]0。等一下刚才我求 L 时先入栈 j3那么 j2 的 L3但手工模拟里 j2 的左边第一个更矮应该是 j1 而不是 j3。重新按代码逻辑走一遍从右往左jm 开始。j3 入栈栈底到栈顶 [3]。j2栈顶 h[3]1 h[2]2不弹L[2]st[top]3j2 入栈栈变成 [3,2]。j1栈顶 h[2]2 ≥ h[1]1弹 j2 记录 L[2]1新栈顶 h[3]1不弹相等不弹因为左侧要求严格小于于是 L[1]st[top]3j1 入栈。但这里 L[1]3 就错了实际 j1 左边没有柱子L 应该是 0。问题出在从右往左找“左边第一个严格小于”时遇到相等的高度不能简单地不弹因为当前的等于高度会挡住更左边更矮柱子的可见性。正确做法是遇到相等的也要弹掉因为“严格小于”要求跳过所有 ≥ 当前高度的柱子。也就是说第二趟循环里弹栈条件也应该是h[st[top]] h[j]但含义变成“当前 j 是被弹出位置的左边界因为它高度 ≥ 被弹出位置不是更矮”。等等那从右往左遇到相等时应该弹掉 j3 吗重新理一遍正确逻辑。从右往左扫描维护一个高度单调递增的栈。对于当前 j要找到左边第一个严格小于 h[j] 的位置。我们从右往左扫栈里存的是已经扫描过的右侧位置。如果栈顶位置的高度 ≥ h[j]它不可能是“严格小于”而且它会阻挡更左侧更矮位置的可见性吗实际上从右往左找左侧边界时我们看的是已经扫过的位置它们都在 j 的右边。这些位置对于求 L[j] 没有直接意义L[j] 应该从还没扫过的左边去确定而不能从右边已经扫过的位置里找。我上面的代码逻辑有误需要修正。正确方法从左往右求 L[j]而不是从右往左。求左边的更矮柱子应该从左往右扫描维护单调递增栈用“弹出时记录边界”的方式从左往右维护栈遇到 h[j] 尝试弹栈弹出元素 top 的左边界 L[top] j因为 h[j] 是 top 右边第一个 ≤ h[top] 的位置而我们需要左边严格小于所以在处理时需要再想想。实际上更清晰的通用写法是直接两趟都用“记录右边界/左边界”但都从左往右配合方向不同处理。让我简化求 R 和 L 都可以用“单调栈 弹出时赋值”的模式只是扫描方向不同但赋值含义对应。一个非常稳妥的写法先从左往右用严格逻辑求出每个 j 的 L[j]再从左往右用非严格逻辑求出 R[j]。L[j] 和 R[j] 都从左往右扫一个维护严格递增栈一个维护非严格递减栈不还是容易晕。让我用最不容易错的官方解法两次扫描求 L 和 R 都用从左到右但栈的维护不同求右边第一个小于等于for (int j 1; j m; j) { while (top 0 h[st[top]] h[j]) { R[st[top]] j; top--; } st[top] j; }注意这里弹出条件是严格大于不是。因为右边要“小于等于”截止遇到相等不弹相等的位置会最终成为后面某次弹出的右边界不对如果相等不弹那么相等的柱子会一直留在栈里当后续遇到更矮的才被弹出右边界就是更矮的位置而非相等位置了。但右侧边界要求是“小于等于”也就是说相等的位置也应该算作右边界截止点。让我重新严格定义一下问题。对于柱子 j我们要找L[j]左边第一个严格小于h[j] 的位置即 h[L] h[j]如果不存在为 0。R[j]右边第一个小于等于h[j] 的位置即 h[R] ≤ h[j]如果不存在为 m1。这样定义的目的是相同高度的柱子从左到右每个柱子的右侧截止点会停在下一个相等柱子处因此区间划分是“左闭右开”保证不重不漏。那么求 R 的单调栈从左往右扫描栈保持高度严格递增遇到 h[j] 时如果栈顶高度 h[j]那么栈顶元素的右侧第一个小于等于它的位置就是 j弹出并记录。如果栈顶高度 ≤ h[j]那 j 不可能成为栈顶的右侧更矮/相等截止点入栈。所以弹出条件是h[st[top]] h[j]遇到相等不弹然后将 j 入栈。但相等不弹的话当 j 自身后续被弹出时它的 R 会被后续更矮位置覆盖这不影响之前那个相等柱子吗之前的相等柱子还在栈里它的 R 还没被赋值等它被弹出时赋的右边界确实是与它相等或更矮的位置正确。模拟[1,2,1]R 求法1j1 入栈 [1]。j2栈顶 h[1]1 ≤ h[2]2不弹入栈 [1,2]。j3h1栈顶 h[2]2 1弹 2 记 R[2]3新栈顶 h[1]1 不大于 1不弹入栈 [1,3]。结束剩余记 R[1]4R[3]4。结果 R [4,3,4]。手算期望j1 右边第一个 ≤1 的位置是 j3R[1] 应为 3j2 右边第一个 ≤2 的位置是 j3R[2]3j3 没有R[3]4。R[1] 错了。为什么 R[1]4 错了因为我在遇到相等时不弹j1 和 j3 高度相等j3 应该作为 j1 的右边界截止点。同理 j3 入栈后j1 一直在栈底它的右边界只能等后续更矮或哨兵结束才记录因此错过了 j3 这个相等截止点。所以右侧“小于等于”的截止点遇到相等时必须处理。正确弹出条件是让当前 j 成为所有被弹出元素的右边界。模拟j1 入栈。j2栈顶 h[1]1 2不弹因为 1 不 ≥ 2入栈 [1,2]。j3栈顶 h[2]2 ≥ 1弹 2 记 R[2]3新栈顶 h[1]1 ≥ 1弹 1 记 R[1]3入栈 [3]。结束R[3]4。结果 R[3,3,4]与手算完全一致。所以求 R 用弹出。被弹出的元素的右边界就是当前 j因为当前 j 的高度 ≤ 被弹出元素的高度是右边第一个“小于等于”。求 L 的边界定义是“严格小于”。用类似的方法从右往左扫描或者从左往右扫描求 L 更直观L[j] 是左边第一个严格小于 h[j] 的位置。从左往右扫维护一个高度严格递增的栈遇到 h[j] 时把栈顶所有高度 ≥ h[j] 的弹出因为它们不能成为任何元素的“严格小于”边界不是对于这些被弹出的元素当前 j 是它们的右侧边界。实际上求 L 可以这样理解对于每个 j我们要找左边第一个严格更矮。从左往右扫维护单调递增栈当处理 j 时栈里的柱子高度从左到右严格递增。栈顶就是 j 左边最近的、高度小于等于的情况。如果栈顶高度 h[j]那 L[j] 栈顶如果栈顶高度 ≥ h[j]那栈顶不可能是 L[j]需要把它弹掉再继续看下一个。所以处理 j 时先弹掉所有高度 ≥ h[j] 的栈顶然后栈顶如果存在就是左边第一个严格小于 h[j] 的位置。模拟[1,2,1]求 Lj1栈空L[1]0入栈 [1]。j2栈顶 h[1]1 2不弹L[2]1入栈 [1,2]。j3栈顶 h[2]2 ≥ 1弹 2新栈顶 h[1]1 ≥ 1弹 1栈空L[3]0入栈 [3]。结果 L[0,1,0]。手算期望j1 左边没有更矮 L0j2 左边第一个更矮是1L1j3 左边第一个严格小于1的没有L0。完全正确。然后再看这和“弹出时记录右边界”的做法是否能统一在求 L 的过程中我们弹掉了 2 和 1有什么边界需要记录吗不需要因为 L 是给当前 j 用的不是给被弹出元素用的。被弹出元素的右侧边界在求 R 时已经记录。所以最终的清晰写法求 R从左往右扫维护单调栈弹出条件h[st[top]] h[j]弹出时记录R[st[top]] j最后栈内剩余记R[st[top]] m1。求 L从左往右扫维护单调栈在入栈之前弹出所有h[st[top]] h[j]然后L[j] st[top]栈空则 0再入栈。这个写法逻辑最清晰推荐使用。代码如下// 求 R[] top 0; for (int j 1; j m; j) { while (top 0 h[st[top]] h[j]) { R[st[top]] j; top--; } st[top] j; } while (top 0) R[st[top--]] m 1; // 求 L[] top 0; for (int j 1; j m; j) { while (top 0 h[st[top]] h[j]) { top--; } L[j] (top 0 ? 0 : st[top]); st[top] j; }你可能会想那求 L 弹出时为什么不记录边界因为弹出的元素是左侧较高的柱子它们的右侧边界已经在 R 阶段处理过了而它们此刻被弹出只是为了让当前 j 能看到更左边的更矮柱子。这里的弹栈和右边界记录无关纯属为查询 L[j] 清理障碍。4.3 数据类型与答案范围先看答案能有多大全.的 n×m 网格合法矩形数 n(n1)/2 × m(m1)/2。当 n2000、m2000 时这个数大约是 2000²/2 × 2000²/2 4×10¹²。所以必须用 long long。如果你用 int样例过了大数据 WA 到怀疑人生。我实际测过 nm1000 的全.网格答案是大约 2.5×10¹¹稳稳超过 int 上限。这个“看上去没多大”的答案范围是最容易踩的坑之一。另外乘法的三个因子 h[j]、j-L[j]、R[j]-j 各自都在 int 范围内但三者相乘可能超过 int。计算时务必先转 long long 再乘ans 1LL * h[j] * (j - L[j]) * (R[j] - j);5. 踩坑实录从 WA 到 AC 的完整排查链路5.1 第一次 WA右侧边界等号处理导致重复计数我第一次写的时候求 R 用了h[st[top]] h[j]作为弹出条件自认为“右边找严格小于”后来发现全部样例输出偏大。排查过程用全 1×4 的.网格测试手算答案是 4×5/210。程序输出 14。手动模拟j1 获得贡献 h×(1−0)×(5−1)4j2 获得 1×1×33j3 获得 2j4 获得 1总数 432110等等输出14说明不是这个问题。再模拟一遍发现我用时 j4 的 R 边界出错导致某些矩形被同时登记。问题根源就是相等高度的柱子之间右侧边界停不下来一个矩形被两个相等高度的柱子各数了一次。把弹出条件改成后全 1×4 输出正好是 10。这个教训值得记住计数类单调栈题等号的两侧分配直接决定“不重不漏”写之前先在草稿纸上定好每个矩形由哪个柱子认领再反向推导弹出条件。5.2 第二次 WAlong long 缺失大数据直接溢出改完边界问题后小样例全过一上 1000×1000 的全.数据就输出负数。我用负数的绝对值对照预期答案发现预期答案大约 2.5×10¹¹int 最大值约 2.1×10⁹差了 100 倍。排查过程其实很快但也很惊险ans h[j] * (j - L[j]) * (R[j] - j);三个 int 相乘在赋值给 long long 之前已经溢出成 int 了。修正方法就是加1LL *强制转换。这题的教训是在竞赛题里只要涉及计数和组合数先估算上界直接开 long long 是基本操作。5.3 第三次 WA哨兵与边界数组初始化有一组数据答案比预期小排查后发现上一行计算留下的 R 数组值在新一行没有被完全覆盖。原因是 h 数组每一行都更新但 L、R 数组只在部分格子被重新赋值如果某轮循环中某些位置没有进入“弹出记录”逻辑残留的旧值就会污染计算。比如 h[j]0 的障碍格子它不会进入统计但它附近柱子的边界如果残留了旧行的值可能出现错误严格来说只要你的代码对每一行重新求一遍 L[j] 和 R[j]对所有 j 都赋值就不会有残留问题。我当时的写法是只统计部分列结果有些列的 L/R 数组没更新。解决办法很简单每行统计前把统计范围严格限定为 1..m并且循环中对每个 j 都显式赋值 L[j] 和 R[j]。如果采用“弹出记录 最终统一赋值栈内剩余”的写法确保每个柱子都恰好在某个时刻被赋一次值即可。还可以用哨兵优化在 h 数组两侧放两个高度为 -1 的虚拟柱子这样左右边界永远存在代码里就不用判断栈空。但需要注意 -1 作为“严格更矮”不会进栈挡住其他柱子可以放心用。如果 h 数组里可能有高度 0 的柱子哨兵用 -1 可以保证不冲突。这个技巧对减少 if 判断很有效。6. 这题的迁移价值从“数矩形”到“计数类单调栈”的通用套路6.1 同类题型的识别特征做多了你会发现这类题有个共同特征在一个二维 0/1 矩阵里数某种合法子矩阵的个数。题型包括最大全 1 子矩阵面积最大、正方形计数、子矩形计数等。P1950 的套路可以迁移到至少两类题最大全 1 矩形面积同样按行枚举底边、维护 h 数组但统计时对每个柱子计算“以它为最低点时宽度 × 高度”的最大值本质就是求 max(h[j] × (R[j]−L[j]−1))。全 1 正方形计数在 h 数组上维护 dp或者用单调栈统计连续段长度的贡献思路完全同源。我后来做类似题目时拿到矩阵题的第一反应就是先尝试“固定底边 高度数组 单调栈”三板斧。这个思维框架一旦建立很多看似新颖的矩阵计数题都可以套进去。6.2 个人体会为什么“代表元素法”是计数题的核心这题最宝贵的收获其实不是单调栈本身而是**“给每个对象安排一个唯一代表让计数不重不漏”**的思想。直方图中有成千上万个矩形如果逐区间枚举会爆炸但给每个矩形指定“最靠右的最低柱子”作为代表就把计数转换成了“每个柱子代表了多少个矩形”的局部问题整体复杂度立刻降到线性。这种思想在组合计数里特别常用等价类划分、最小表示法、双指针划分区间本质上都在做同一件事——给每个计数对象找一个唯一的、容易计算的归属。我在实际解决问题时体会到遇到计数问题可以先问自己三个问题每个对象能不能有一个唯一的“代表”这个代表的“管辖范围”是不是容易计算代表的数量是否远小于对象的数量如果三个问题的答案都是肯定的那大概率可以用某种数据结构最常见就是单调栈在 O(n) 或 O(n log n) 内完成计数。P1950 只是这个思想的一个漂亮外壳。另外再提一个做题习惯这类公式题千万别只看答案记住结论。我建议每个公式都自己拿小样例穷举验证一遍再想清楚“为什么这个矩形不会跑到别的柱子的账上”。想通了以后你才算真正掌握而不是背了一个神秘公式。