題意：給一個01矩陣，求其中極大全1子矩陣的個數(shù)，極大指的是這個矩陣不能再往擴展。

題解：枚舉每個子矩陣的底邊，維護一個單調棧（嚴格遞增）。

紅色柱子代表棧中元素，藍色表示即將刪除的元素

如上圖所示，棧中維護往上拓展的高度up和以這一塊為最右端往左擴展的位置pos。顯然pos是左邊第一個大于等于自己高度up的值，在push的過程中會一直等于這條柱子自己的位置。此外由于我們考慮的是每個矩陣的底邊，而如果當前行的下一行仍然為1，則說明矩陣能往下擴展，跳過這些情況。

被彩色粗線框起來的是合法矩形

維護最后一個不能往下擴展的格子ma，每次pop的柱子如果它的pos小于等于ma，則說明我們能找到一個以當前枚舉的行為底邊的極大子矩陣。

往上拓展的高度up這個值可以通過類似前綴和的操作預處理。從而總復雜度

#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;
}