P1950. 长方形

发表于 2024-01-02 分类于洛谷阅读次数： Waline：本文字数： 390 阅读时长 ≈ 1 分钟

考点

单调栈
悬线法

题解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 50;
ll ans;
char c[maxn][maxn];
int n, m, top, st[maxn], h[maxn], l[maxn], r[maxn];

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      cin >> c[i][j];
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) h[j] = c[i][j] == '.' ? h[j] + 1 : 0;
    //左开右开区间
    //求向右最大延伸，维护不减单调栈
    top = 0;
    for (int j = 1; j <= m; ++j) {
      while (top && h[st[top]] > h[j]) r[st[top--]] = j;
      st[++top] = j;
    }
    while (top) r[st[top--]] = m + 1;
    //求向左最大延伸，维护递增单调栈
    top = 0;
    for (int j = m; j >= 1; --j) {
      while (top && h[st[top]] >= h[j]) l[st[top--]] = j;
      st[++top] = j;
    }
    while (top) l[st[top--]] = 0;
    for (int j = 1; j <= m; ++j) ans += 1ll * h[j] * (j - l[j]) * (r[j] - j);
  }
  cout << ans;
  return 0;
}