P1950
Aryper
·
·
个人记录
长方形
我们统计对与底边为某条边的所有的长方形的数量。
定义 h_i 为当前列的高度。
定义 l_i 为 i 左边第一个高度不大于 h_i 的位置，r_i 为 i 右边第一个高度小于 h_i 的位置。
那么我们就可以统计 (i-l_i)(r_i-i)h_i 进入答案。
时间复杂度 $O(n^2)$。
代码：
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const ll N=1e3;
ll n,m,top,ans;
ll a[N+5][N+5],h[N+5][N+5],l[N+5],r[N+5],stk[N+5];
string s;
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
return ret*f;
}
void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {
do{buf[++len]=x%10+48;x/=10;}while(x);
}
else {
putchar('-');
do{buf[++len]=-(x%10)+48;x/=10;}while(x);
}
while(len>=0) putchar(buf[len--]);
}
int main() {
n=read();m=read();
for(ll i=1;i<=n;i++) {
cin>>s;
for(ll j=0;j<m;j++) {
if(s[j]=='.') a[i][j+1]=1;
else a[i][j+1]=2;
if(a[i][j+1]==1) {
h[i][j+1]=h[i-1][j+1]+1;
}
if(a[i][j+1]==2) {
h[i][j+1]=0;
}
}
}
for(ll i=1;i<=n;i++) {
top=0;stk[top]=0;
for(ll j=1;j<=m;j++) {
while(top>0&&h[i][j]<h[i][stk[top]]) top--;
l[j]=stk[top];stk[++top]=j;
}
top=0;stk[top]=m+1;
for(ll j=m;j>=1;j--) {
while(top>0&&h[i][j]<=h[i][stk[top]]) top--;
r[j]=stk[top];stk[++top]=j;
}
for(ll j=1;j<=m;j++) {
ans+=h[i][j]*(j-l[j])*(r[j]-j);
}
}
write(ans);
return 0;
}
```