城市游戏 这题NOI出过 叫什么 玉蟾宫
单调栈。。。。。 其实还能用悬线法处理
找到 每层 每个 相对这个数据的最远的左端 右端 * 自己的高度即可
之后 补充一个 悬线法解的题

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000 + 5;

int n, m;
int h[maxn][maxn];
int q[maxn], l[maxn], r[maxn];

int sol(int l[], int a[]){
    a[0] = -1;
    int t = 0;
    for(int i = 1; i <= m; i ++ ) {
        while(a[q[t]] >= a[i]) t --;
        l[i] = q[t] + 1;
        q[ ++ t ] = i;
    }
}

int work(int a[]){
    sol(l, a);
    reverse(a + 1, a + 1 + m);
    sol(r, a);
    reverse(a + 1, a + 1 + m);
    int res = 0;
    for(int i = 1; i <= m; i ++ ) {
        int le = l[i];
        int ri = m + 1 - r[m - i + 1];
        res = max(res, a[i] * (ri - le + 1));
    }
    return res;
}

char mp[maxn][maxn];

int main(){
    cin >> n >> m;
    int ans = 0;
    for(int i = 1; i <= n; i ++ ) {
        for(int j = 1; j <=m; j ++ ) {
            cin >> mp[i][j];
            if(mp[i][j] == 'F') h[i][j] = h[i - 1][j] + 1;
            else continue;
        }
        ans = max(ans, work(h[i]));
    }

    cout << ans * 3 << endl;
    return 0;
}

P1169 [ZJOI2007]棋盘制作 2题一样 悬线法

include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 2e3+10;
const int INF= 0x3f3f3f3f;
const int mod = 1000000007;

int n,m,k,ans;
int a[maxn];

int l[maxn][maxn],r[maxn][maxn],up[maxn][maxn];
int mp[maxn][maxn];
int main() {
cin>>n>>m;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
cin>>mp[i][j];
l[i][j]=r[i][j]=j;
up[i][j]=1;
}
}

for(int i=1; i<=n; i++) for(int j=2; j<=m; j++)
        if(mp[i][j-1]^mp[i][j]) l[i][j]=l[i][j-1];

for(int i=1; i<=n; i++) for(int j=m-1; j>=1; j--)
        if(mp[i][j]^mp[i][j+1]) r[i][j]=r[i][j+1];

int ans1=0,ans2=0;
for(int i=1; i<=n; i++) {
    for(int j=1; j<=m; j++) {
        if( i>1 && mp[i-1][j]^mp[i][j]) {
            l[i][j]=max(l[i-1][j],l[i][j]);
            r[i][j]=min(r[i-1][j],r[i][j]);
            up[i][j]=up[i-1][j]+1;
        }
        int len=r[i][j]-l[i][j]+1;
        int h=min(up[i][j],len);
        ans1=max(h*h,ans1);
        ans2=max(len*up[i][j],ans2);
    }
}
cout<<ans1<<endl<<ans2<<endl;
return 0;

}