題意：給一個(gè)01矩陣单雾，求其中極大全1子矩陣的個(gè)數(shù)赚哗，極大指的是這個(gè)矩陣不能再往擴(kuò)展。
題解：枚舉每個(gè)子矩陣的底邊硅堆，維護(hù)一個(gè)單調(diào)棧（嚴(yán)格遞增）屿储。
紅色柱子代表?xiàng)Ｖ性兀{(lán)色表示即將刪除的元素
如上圖所示渐逃，棧中維護(hù)往上拓展的高度up和以這一塊為最右端往左擴(kuò)展的位置pos够掠。顯然pos是左邊第一個(gè)大于等于自己高度up的值，在push的過程中會(huì)一直等于這條柱子自己的位置茄菊。此外由于我們考慮的是每個(gè)矩陣的底邊疯潭，而如果當(dāng)前行的下一行仍然為1赊堪，則說明矩陣能往下擴(kuò)展，跳過這些情況竖哩。
被彩色粗線框起來的是合法矩形
維護(hù)最后一個(gè)不能往下擴(kuò)展的格子ma哭廉，每次pop的柱子如果它的pos小于等于ma，則說明我們能找到一個(gè)以當(dāng)前枚舉的行為底邊的極大子矩陣相叁。
往上拓展的高度up這個(gè)值可以通過類似前綴和的操作預(yù)處理遵绰。從而總復(fù)雜度
#ifdef ONLINE_JUDGE
#include <bits/stdc++.h>
#endif
using namespace std;
using pii = pair<int, int>;
const int maxn = 3005;
char g[maxn][maxn];
int sum[maxn][maxn];
int main()
{
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; I++)
{
cin >> (g[i] + 1);
}
for (int i = 1; i <= n; I++)
{
for (int j = 1; j <= m; j++)
{
if (g[i][j] == '1')
sum[i][j] = sum[i - 1][j] + 1;
}
}
int ans = 0;
for (int i = 1; i <= n; I++)
{
stack<pii> s;
int ma = -1;
for (int j = 1; j <= m + 1; j++)
{
int pos = j;
while (!s.empty() && s.top().first > sum[i][j])
{
if (s.top().second <= ma)
{
ans++;
}
pos = s.top().second;
s.pop();
}
if (!sum[i + 1][j])
ma = j;
if (sum[i][j] && (s.empty() || s.top().first < sum[i][j]))
{
s.emplace(sum[i][j], pos);
}
}
}
cout << ans << endl;
}
