前置知识
单调栈
题意
对只由1组成的子矩形计数。
思路
矩形可由左上及右下2个点确定。
暴力遍历
复杂度 $O(n^2 m^2)$ 起步。
优化
该计数问题可分解为2个部分。
- $O(nm)$遍历每个点；
- 对以该点为左上顶点或右下顶点（本题解使用后者）的矩形计数。即：从该点向左上方尽可能拓展，直至遇到边界或
[0]方格，求最大覆盖面积。
考虑第2步中每个点的计数是否可以通过前面已计算出的部分加速。
在向左上方拓展时，若一个方格是 [0] ，那么该方格正左、正上及左上方都一定无法被覆盖，因此列高度从右向左来看是非严格递减的，因此考虑单调类数据结构。
在从左向右扫描时可能出现更低的方格使前面结果部分无效，新 [0] 方格有迫使前面 [0] 方格出队的可能。具体来说，某个 [0] 方格会使前面所有高于它的方格无效，同时保留更低的方格。正好符合单调栈严格递减的特点。
在对每一行进行扫描时，先将该列最高的 [0] 方格压入单调栈，再计算该列的覆盖面积。
单调栈的加速在于：只需要计算从当前最高的 [0] 方格到次高的 [0] 方格之间的覆盖面积，即 横坐标差值 乘 该列最高 [0] 方格高度与该方格高度之差，而次高 [0] 方格以左的部分都可以直接使用之前的计算结果，即次高 [0] 方格所在列与当前行交点这个格子的覆盖面积。
正确性是显然的。次高 [0] 方格所在列与当前行交点这个格子能覆盖的点都能被当前点覆盖，而最高 [0] 方格到次高 [0] 方格间显然最高只能到最高 [0] 方格的高度-1。
注意事项
[0]方格高度依次上升，纵坐标依次下降，因此单调栈应为严格下降
实现
压行有点狠...
#include <iostream>
#include <algorithm>
using namespace std;
long long r;
int n, m, st, l[3005], s[3005], c[3005];
bool g[3005][3005];
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> g[i][j];
for (int j = 0; j < m; j++)
l[j] = -1;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
for (((j == 0) ? st = 0 : st),
(g[i][j] ? l[j] : l[j] = i);;)
if ((st == 0 || l[s[st-1]] > l[j]) ?
(
s[st++] = j,
r += (c[st] = (st == 1) ?
(j + 1) * (i - l[s[st - 1]])
:c[st - 1] + (j - s[st - 2]) * (i - l[s[st - 1]])),
true
) : (
--st,
false
))
break;
cout << r;
return 0;
}