做题记录整理栈7 P1950 长方形（2022/10/11）

P1950 长方形
玉蟾宫升级版

#include<bits/stdc++.h>
#define for1(i,a,b) for(int i = a;i<=b;i++)
#define ll long long
#define mp(a,b) make_pair(a,b)
using namespace std;
char s;
ll l[1005],r[1005],h[1005],k[1005],n,m,top;
int a[1005][1005];
ll ans;
void jl()
{
    top=0;
    for(int i=m;i>=1;i--)
	{
        while(top!=0&&h[i]<=h[k[top]]) l[k[top]]=i,top--;
        top++;
        k[top]=i;
    }
    while(top) l[k[top]]=0,top--;
}
void jr()
{
    top=0;
    for(int i=1;i<=m;i++)
	{
        while(top!=0&&h[i]<h[k[top]]) r[k[top]]=i,top--;
        top++;
        k[top]=i;
    }
    while(top) r[k[top]]=m+1,top--;
}
int main()
{
    cin>>n>>m;
    for1(i,1,n)
        for1(j,1,m)
		{
            cin>>s;
            if(s=='*') 
			    a[i][j]=1;
        }
    for1(i,1,n)
	{
        for1(j,1,m)
		{
		    h[j]++;
			if(a[i][j]) h[j]=0;
		}
        jl();jr();
        for1(j,1,m) ans+=(j-l[j])*(r[j]-j)*h[j];
    }
    cout<<ans;
}