洛谷题单指南-常见优化技巧-P1950 长方形

原题链接：https://www.luogu.com.cn/problem/P1950

题意解读：在一张n*m个格子的纸上，从没有画过的格子中剪出长方形的方案数。

解题思路：

1、暴力做法

枚举所有的子矩阵O(n^4)，然后用二维前缀和计算子矩阵的和，通过和来判断子矩阵是否全部是'.'。

2、优化做法

针对每一行进行处理，计算包含每一行每一个格子的长方形数量。

考虑每一个'.'的格子的悬线（悬线的应用，可以参考：https://www.cnblogs.com/jcwy/p/18361265）

设某一行每一列j的悬线高度h[j]，每一列左边第一个小于等于h[j]的位置是l[j]，右边第一个小于h[j]的位置是r[j]

如下图，

假设已处理到第3行，第3行每列点的悬线覆盖的是绿色区域，所以只用考虑绿色区域一共组成多少长方形。

如何计算绿色区域长方形的数量？

先考虑第1列：

h[1] = 1，l[1] = 0, r[1] = 3

解读：第一列悬线高度是1，左边第一个小于等于h[1]的位置是0，右边第一个小于h[1]的位置是4

所以：覆盖第一列的所有长方形数量为(1 - l[1]) * (r[1] - 1) * h[1] = 3，也就是第一列、第一二列、第一二三列三种情况。

再考虑第2列：

h[2] = 2, l[2] = 1, r[2] = 3

解读：第二列悬线高度是2，左边第一个小于等于h[2]的位置是1，右边第一个小于h[2]的位置是3

所以：覆盖第二列的所有长方形数量为(2 - l[2]) * (r[2] - 2) * h[2] = 2，也就是第二列、第二列+上一行的第二列两种情况。

再考虑第3列：

h[3] = 1, l[3] = 1, r[3] = 4

解读：第三列悬线高度是1，左边第一个小于等于h[3]的位置是1，右边第一个小于h[3]的位置是4

所以：覆盖第三列的所有长方形数量为(3 - l[3]) * (r[3] - 3) * h[3] = 2，也就是第三列、第三二列两种情况。

以上分析，就是包含第3行所有列的长方形的数量，不重不漏。

下面问题就在于如何计算l[]，r[]

要计算j左边第一个小于等于h[j]的位置l[j]，以及j右边第一个小于h[j]的位置r[j]，可以借助单调栈。

100分代码：

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

const int N = 1005;
int n, m;
char a[N][N];
int h[N]; //h[j]表示某行第j列点的悬线高度
int l[N]; //l[j]表示某行第j列点左边第一个悬线高度小于等于h[j]的位置
int r[N]; //r[j]表示某行第j列点右边第一个悬线高度小于h[j]的位置
int stk[N], top;
long long ans;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            if(a[i][j] == '.') h[j] = h[j] + 1; //计算(i,j)的悬线高度
            else h[j] = 0;
        }

        //通过单调栈计算第i行每个点j左边第一个小于等于h[j]的位置，没有的话就是0
        top = 0;
        for(int j = 1; j <= m; j++)
        {
            while(top && h[stk[top]] > h[j]) top--;

            l[j] = stk[top];
            stk[++top] = j;
        }

        //通过单调栈计算第i行每个点j右边第一个小于h[j]的位置，没有的话就是m+1
        top = 0;
        for(int j = m; j >= 1; j--)
        {
            while(top && h[stk[top]] >= h[j]) top--;

            if(top) r[j] = stk[top];
            else r[j] = m + 1;
            stk[++top] = j;
        }

        //更新答案
        for(int j = 1; j <= m; j++)
            ans += (j - l[j]) * (r[j] - j) * h[j];
    }

    cout << ans;

    return 0;
}