题意:
一个老村花写的题意:
分析:
很简单的单调栈水题。。。
从左往右依次计算每一行。。。
然后就可以用单调栈+等差数列求和即可。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 2010
using namespace std;
typedef long long ll;
char s[MAXN][MAXN];
ll h[MAXN][MAXN];
int st[MAXN],top,w[MAXN];
ll adds(ll l,ll r){
ll sum=r-l+1ll;return (l+r)*sum/2ll;
}
int main(){
int n,m;SF("%d%d",&n,&m);for(int i=1;i<=n;i++)SF("%s",s[i]+1);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
if(s[i][j]=='#')h[i][j]=0;elseh[i][j]=h[i-1][j]+1; }ll ans=0;for(int i=1;i<=n;i++){
top=0;ll sum=0,tot=0;for(int j=1;j<=m;j++){
int wd=0;while(top>0&&h[i][st[top]]>h[i][j]){
sum-=adds(wd+1,wd+w[top])*adds(0,h[i][st[top]]);wd+=w[top];tot-=w[top]*adds(0,h[i][st[top]]);top--;}wd++;st[++top]=j;w[top]=wd;sum+=adds(0,wd)*adds(0,h[i][j]);sum+=tot;
// PF("{%d %d %lld %lld}\n",i,j,sum,tot);tot+=w[top]*adds(1,h[i][st[top]]);
// PF("[%d %d]\n",st[top],w[top]);ans+=sum;}}PF("%lld",ans);
}