悬线法

使用一维悬线法找极大子矩形，通过极大子矩形统计矩形数量。

我一般使用悬线法找位置 $(i,j)$ 可以向上延伸的最大高度 $h_{i,j}$，在矩形高度为 $h_{i,j}$ 的情况下从 $(i,j)$ 最长可以向左延伸到的列 $l_{i,j}$ 和最长可以向右延伸到的列 $r_{i,j}$。然而这样统计长方形数量会不仅会算重还会算漏，因为当 $h_{i,j} \leq h_{i,j-1}$ 时可以用 $l_{i,j-1}$ 更新 $l_{i,j}$，当 $h_{i,j} \leq h_{i,j+1}$ 时又可以用 $r_{i,j+1}$ 更新 $r_{i,j}$，如此一来两个位置对应的极大子矩形可能是一样的。

为了不重不漏地计算答案，强制一边不能在相等高度的情况下扩展。把用 $r_{i,j+1}$ 更新 $r_{i,j}$ 的条件更改为 $h_{i,j} < h_{i,j+1}$，这样做之后任意两个位置对应的极大子矩形都是不同的。

位置 $(i,j)$ 对答案的贡献为包含 $(i,j)$ 且在 $(i,j)$ 对应的极大子矩形中的的矩形数量，即 $h_{i,j} (j - l_{i,j} + 1) (r_{i,j} - j + 1)$，时间复杂度 $O(nm)$。

#include<bits/stdc++.h>
using namespace std;
int n,m,h[1'005][1'005],l[1'005][1'005],r[1'005][1'005];
char s[1'005][1'005];
long long ans;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
        while(s[i][j]!='.'&&s[i][j]!='*') s[i][j]=getchar();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) if(s[i][j]=='.') h[i][j]=h[i-1][j]+1;
        for(int j=1;j<=m;j++) if(s[i][j]=='.') l[i][j]=j,r[i][j]=j;
        for(int j=1;j<=m;j++) if(s[i][j]=='.')
            while(l[i][j]!=1&&h[i][l[i][j]-1]>=h[i][j]) l[i][j]=l[i][l[i][j]-1];
        for(int j=m;j>=1;j--) if(s[i][j]=='.')
            while(r[i][j]!=m&&h[i][r[i][j]+1]>h[i][j]) r[i][j]=r[i][r[i][j]+1];
        for(int j=1;j<=m;j++) ans+=1ll*h[i][j]*(j-l[i][j]+1)*(r[i][j]-j+1);
    }
    printf("%lld\n",ans);
    return 0;
}