有一面 $n$ 行 $m$ 列的矩形墙，被划分为 $n\times m$ 个区域。墙上有些区域有钉子，用 $\texttt{\#}$ 表示；其他的区域没有钉子，用 $\texttt{.}$ 表示。

现在要在墙上挂画。我们说一种挂画方式是合法的，当且仅当：

• 画占据墙上的一个矩形区域；
• 画占据的区域中至多一个区域存在钉子。

求出有多少种合法的挂画方式。

$n, m \le 500$。

题解

本题涉及二维前缀和，滑动窗口。难度为普及。

$n^4$ 的暴力此处不再赘述。考虑如何优化到 $n^3$。

假设当前枚举的区域上顶部为 $a$ 行，下底部为 $b$ 行，左边所在列为 $x$，右边所有的列为 $y$，现在在固定 $a、b、x$ 的条件下，找到 $y$ 满足条件的最大值 $Y$。那么，所有的 $y \in [x, Y]$ 均满足条件，于是答案增加 $Y - x + 1$。接下来，我们将左边所在的列 $x$ 增加 $1$，$y$ 继续右移，找到可能的最大值。重复此步骤，直到 $x > m$ 为止。

参考代码

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

int A[505][505];
int n, m;

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      A[i][j] += A[i - 1][j];
      char ch; cin >> ch;
      if (ch == '#') A[i][j]++;
    }
  }

  long long ans = 0;
  for (int a = 1; a <= n; a++) {
    for (int b = a; b <= n; b++) {
      int y = 0;
      int sum = 0;
      for (int x = 1; x <= m; x++) {
        while (y + 1 <= m && sum + A[b][y + 1] - A[a - 1][y + 1] <= 1) {
          sum += A[b][y + 1] - A[a - 1][y + 1]; 
          y++;
        }
        ans += y - x + 1;
        sum -= A[b][x] - A[a - 1][x];
      }
    }
  }
  cout << ans << endl;
}