子矩阵问题

问题描述：在一个给定的 $n \times m$ 的矩形中，求出满足某些要求的矩形的最值或数量。

扫描法

单调栈法

枚举每一点往上能走的最大步数，问题转化为求解单位宽度、高度不等的连续排列矩形所能构成的矩形的最大面积。

可以观察到，当矩形高度递增时，每一个高度都是最大面积矩形的备选答案；若出现高度小于上一个的矩形，那么对于之后的矩形，所组成的矩形高度受限于这个高度较小的矩形。于是用单调栈维护一个高度递增的矩形，当出现高度较小的矩形时，将其不断与之前的高度比它大的矩形在宽度上进行合并，同时更新答案。

例题：子矩阵计数

悬线法

定义以下概念：

• 有效子矩形：满足要求的矩形。
• 极大子矩形：各个边都不能向外扩展的有效子矩形。
• 最大子矩形：最大的极大子矩形。

显然，在所有矩形中，只有极大子矩形可能成为答案，而每个极大子矩形必然存在至少一个不属于其他极大子矩形的点（用反证法易证），可以对每一个点维护这个点在各个方向能达到的最远处。

令 $\mathrm{left}_{i,j}$ 表示从 $(i,j)$ 往左能达到的最左的位置，$\mathrm{right}_{i,j}$ 表示从 $(i,j)$ 往右能达到的最右的位置，$\mathrm{up}_{i,j}$ 表示从 $(i,j)$ 往上能走的最大步数。

先递推得到 $\mathrm{left}$ 和 $\mathrm{right}$ 的值。然后从上到下，从左到右枚举每一个点 $(i,j)$：如果这个点可以向上扩展，$\mathrm{up}_{i,j} \leftarrow \mathrm{up}_{i-1,j}$，$\mathrm{left}_{i,j} \leftarrow \max\{\mathrm{left}_{i-1,j},\mathrm{left}_{i,j}\}$，$\mathrm{right}_{i,j} \leftarrow \min\{\mathrm{right}_{i-1,j},\mathrm{right}_{i,j}\}$；否则 $\mathrm{up}_{i,j} \leftarrow 1$。可以证明，每个极大子矩形都可以被在这个矩形的最下面一行的点统计到。（用反证法易证）

例题：最大子矩形