[Leaf] [P1950] 长方形

p1950-长方形---洛谷">P1950 长方形 - 洛谷

1. 题面梗概

中译中: 给你一个黑白格点图，问你这里面一共能圈出多少个纯白的长方形？

2. 逻辑推导

直觉: 暴力数肯定不行，得换个思路。如果我固定长方形的底部在某一行，往上看，这不就是一个个柱状图吗？这就是一个 悬线法 + 贡献法 的典型应用。

我们分析一下，如果只有一行，问题就是要找有多少子区间，这很简单。但如果问的是二维的问题呢？我们可以枚举每一行作为长方形的底边。

对于第 $i$ 行的每个点 $j$，它能向上延伸的连续白格高度 $h[j]$ 就是一个悬线。

接下来我们考虑怎么统计，在第 $i$ 行，我们看到的是一个柱状图，在这个柱状图中，每个局部最低点都限制了以它为顶点的长方形宽度。

• 每一个长度为 $H$ 的柱子，如果它是某个区间内的最小值，那么它能贡献的长方形数量就是 $H \times$ (左边比它高的跨度) $\times$ (右边比它高的跨度)。

• 为了快速找到每个柱子左右的最值，我们用单调栈来维护。

3. 代码实现

▶

AcCode 朴素解法

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1000 + 50;

char mat[maxn][maxn];
int h[maxn];
int n, m;

int main()
{	
    cin >> n >> m;
    long long ans = 0;
    for( int i = 1; i <= n; ++ i )
    {
        for( int j = 1; j <= m; ++ j )
        {
            char tmp;
            cin >> tmp;
            if( tmp == '.' ) h[j] ++;
            else h[j] = 0;
        }
        for( int j = 1; j <= m; ++ j )
        {
            int cur = h[j];
            for( int k = j; k <= m; ++ k )
            {
                if( !h[k] ) break;
                cur = min( cur, h[k] );
                ans += cur;    
            }
        }
    }
    
    cout << ans << '\n';
    return 0;
}

▶

AcCode 单调栈优化

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 1000 + 5;

int n, m;
int h[maxn], l[maxn], r[maxn];

ll solve( )
{
    stack< int > stk;
    for( int i = 1; i <= m ; ++ i )
    {
        while( !stk.empty( ) && h[stk.top( )] >= h[i] ) stk.pop( );
        l[i] = stk.empty( ) ? 0 : stk.top( );
        stk.push( i );
    }

    while( !stk.empty( ) ) stk.pop( );
    for( int i = m; i >= 1; -- i )
    {
        while( !stk.empty( ) && h[stk.top( )] > h[i] ) stk.pop( );
        r[i] = stk.empty( ) ? m + 1 : stk.top( );
        stk.push( i );
    }

    ll res = 0;
    for( int i = 1; i <= m; ++ i )
    {
        res += 1ll * h[i] * ( i - l[i] ) * ( r[i] - i );
    }
    return res;
}

int main( )
{
    cin >> n >> m;

    ll ans = 0;
    for( int i = 1; i <= n; ++ i )
    {
        for( int j = 1; j <= m; ++ j )
        {
            char c;
            cin >> c;
            if( c == '.' ) h[j] ++;
            else h[j] = 0;
        }
        ans += solve( );
    }
    cout << ans << '\n';
    return 0;
}

4. 复盘

• 复杂度：$O( N \cdot M^2 ) \to O( N \cdot M )$

• Trick：这题其实我们区间处理去重的时候，可以采用一边取等，一边不取等的方式。

• 关联笔记: 单调栈