洛谷P3400题解：单调栈统计全1子矩阵的巧妙方法

7个月前 (07-25)洛谷题解960

一、问题描述

给定一个由0和1组成的n×m矩阵，要求统计所有全1子矩阵的数量。这个问题可以转化为对每个位置计算以其为右下角的子矩阵数量。

二、算法核心思想

高度数组预处理：将问题转化为柱状图问题
单调栈应用：高效计算每个位置的左右边界
组合数学计算：利用边界信息统计子矩阵数量

三、完整代码实现（带详细注释）

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

const int MAXN = 3005;
int h[MAXN][MAXN]; // 高度数组，记录每个位置向上连续1的个数
int n, m;

// 计算单行中的全1子矩阵数
long long solveRow(int row) {
    stack<int> st;
    long long res = 0;
    vector<int> left(m+2), right(m+2);
    
    // 左边界计算：找到每个位置左边第一个比它小的位置
    for(int j = 1; j <= m; j++) {
        while(!st.empty() && h[row][st.top()] >= h[row][j]) {
            st.pop();
        }
        left[j] = st.empty() ? 0 : st.top();
        st.push(j);
    }
    
    // 清空栈
    while(!st.empty()) st.pop();
    
    // 右边界计算：找到每个位置右边第一个比它小的位置
    for(int j = m; j >= 1; j--) {
        while(!st.empty() && h[row][st.top()] > h[row][j]) {
            st.pop();
        }
        right[j] = st.empty() ? m+1 : st.top();
        st.push(j);
    }
    
    // 计算结果：以当前位置为最高点的子矩阵数量
    for(int j = 1; j <= m; j++) {
        if(h[row][j] == 0) continue;
        res += (long long)(j - left[j]) * (right[j] - j) * h[row][j];
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    long long ans = 0;
    
    // 预处理高度数组：计算每个位置向上连续1的个数
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            char c; cin >> c;
            if(c == '1') h[i][j] = h[i-1][j] + 1;
            else h[i][j] = 0;
        }
    }
    
    // 逐行计算：对每一行应用单调栈算法
    for(int i = 1; i <= n; i++) {
        ans += solveRow(i);
    }
    
    cout << ans << endl;
    return 0;
}