悬线法、极大子矩形类问题

二维悬线法维护符合条件的极大子矩形取最大面积。具体地，维护 $h_{i,j}$ 表示以第 $i$ 行为底边且包含位置 $(i,j)$ 的矩形的最大高度；维护 $l_{i,j}$ 表示以第 $i$ 行为底边且包含位置 $(i,j)$，高为 $h_{i,j}$ 的矩形从第 $j$ 列开始向左最多包含的列数；维护 $r_{i,j}$ 表示以第 $i$ 行为底边且包含位置 $(i,j)$，高为 $h_{i,j}$ 的矩形从第 $j$ 列开始向右最多包含的列数。答案必定是某一个合法极大子矩形的面积，也就是 $\max\limits_{i=1}^{n} \max\limits_{j=1}^{m} h_{i,j} \times (l_{i,j} + r_{i,j} - 1)$。最大的子正方形从最大子矩阵里取。

时间复杂度 $O(nm)$。

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