仓鼠窝 题解

数值范围

全 1 矩阵的答案最大，为

[ \frac{n(n+1)m(m+1)}4. ]

当 $n=m=3000$ 时答案为 $20263502250000$，总答案及中间贡献必须使用 64 位有符号整数。

思路

逐行扫描。令 $h_j$ 表示以当前行为底、列 $j$ 连续向上的 1 的数量；当前格为 1 时高度加一，为 0 时清零。

固定当前底行和右端列 $r$。若左端列为 $l$，可选的顶行数量恰为

[ \min(h_l,h_{l+1},\ldots,h_r). ]

所以所有以当前格为右下角的合法矩形数，等于所有后缀最小高度之和。

做法

用单调递增栈维护二元组“高度、宽度”。宽度表示有多少个连续左端点的后缀最小值等于该高度，并维护这些后缀最小值之和 $S$。插入新高度 $h$ 时，把所有高度不小于 $h$ 的栈段弹出：从 $S$ 中减去旧的高度乘宽度，并把宽度合并到新段。再压入 $(h,w)$，把 $hw$ 加入 $S$，最后把 $S$ 加入答案。

每个栈段精确代表一组后缀最小值；新高度只会把旧最小值不小于它的后缀统一降为它。故更新后 $S$ 仍等于所有后缀最小高度之和。每个矩形又有唯一的底行和右端列，逐格累加不重不漏。

复杂度

每个栈段每行至多进栈、出栈一次，时间复杂度为 $O(nm)$，空间复杂度为 $O(m)$。

部分分

• 若坏格至多一个，全 1 矩阵用总矩形公式；唯一坏格位于 1-based 坐标 $(r,c)$ 时，减去 $r(n-r+1)c(m-c+1)$，得到 20 分。
• 当 $n,m\le30$ 时，用二维前缀和枚举四条边，复杂度 $O(n^2m^2)$，得到 10 分。
• 当 $n,m\le200$ 时枚举上下边界，维护各列是否全 1，并按连续 1 段计数，复杂度 $O(n^2m)$；它同时通过上一规模层，累计 40 分。
• 合并“坏格至多一个”的公式与行对枚举，可累计 60 分。