题目大意

给定一个 $N \times M$ 的矩阵，每个位置 $(i,j)$ 有一个海拔值 $a_{i,j}$。要求统计所有内部值全相等的矩形子矩阵的个数。换句话说，需要找出所有满足以下条件的矩形区域 $[r_1,r_2] \times [c_1,c_2]$：该矩形内所有格子的海拔值完全相同。

算法思路

问题分析

直接枚举所有子矩阵的时间复杂度为 $O(N^2M^2)$，在 $N,M \leq 1000$ 时不可行。需要利用矩阵的局部性质进行优化。

核心思想：悬线法 + 单调栈

1. 列连续高度预处理

定义 l[j] 表示在第 $i$ 行时，从位置 $(i,j)$ 向上连续相同值的最大长度：

如果 $a[i][j] = a[i-1][j]$，则 l[j] = l[j] + 1

否则 l[j] = 1

这实际上是以当前行为底边，向上延伸的同值矩形的最大高度。

2. 行连续性处理

由于要求矩形内所有值相等，当同行相邻列值不同时，必须开始新的区间。因此按行处理时，需要根据值的变化划分区间。

3. 单调栈维护历史信息

使用单调栈来维护当前区间内的列高度信息：

栈中存储列索引，对应的 l[j] 值单调递增

当新列的 l[j] 小于栈顶列的 l[j] 时，弹出栈顶并计算该列不再能贡献的矩形数量

栈中每个元素代表一个"高度块"，相同高度的列可以一起处理

4. 贡献计算机制

对于每个位置 $(i,j)$，计算以该位置为右下角的所有合法子矩阵数量：

使用前缀和数组 s[ss] 快速累加不同高度组合产生的矩形数量

对于高度为 $h$、宽度为 $w$ 的矩形块，其贡献为 $h \times w$ 相关的组合数

通过单调栈的弹出操作，确保只统计值相同的连续区域

算法复杂度分析

时间复杂度：$O(N \times M)$，每个元素入栈出栈各一次

空间复杂度：$O(M)$，用于存储列高度和单调栈

总结

本题是全等值子矩阵计数问题，主要考察：

问题转化能力：将二维矩阵统计转化为一维高度处理

悬线法应用：通过列连续高度记录向上延伸的同值区域

单调栈优化：高效维护历史高度信息，避免重复计算

贡献分析法：以每个位置为基准统计其贡献的矩形数量

该解法通过 $O(NM)$ 的复杂度解决了看似 $O(N^2M^2)$ 的问题，体现了降维思想和数据结构优化在矩阵统计问题中的重要作用。悬线法结合单调栈的技巧可以推广到其他需要统计满足特定条件的子矩阵数量的问题中。