最大面积（冬季每日一题 8）

给定一个 的 矩阵，矩阵下标从

有 个询问，第 个询问为：将矩阵中 () 的元素改成 之后，只包含

注意：

1. 每次询问均是独立的。
2. 询问方格内元素可能本来就是 。
3. 子矩阵的面积是指矩阵的大小。

输入格式
第一行包含两个整数 。

接下来 行，每行包含 个

再一行包含整数 。

接下来 行，每行包含 个整数 ()。

输出格式
每个询问输出一行一个结果，表示最大面积。

数据范围
对于 20% 的数据，
对于 50% 的数据，
对于 100% 的数据，
输入样例：

4 2
10
11
11
11
3
0 0
2 0
3 1

输出样例：

6
3
4

#include<iostream>
#include<cstring>

using namespace std;

const int N = 2010;

int n, m;
int l[N], r[N], q[N], s[N][N];
int U[N], D[N], L[N], R[N];
char g[N][N];

int calc(int h[], int n){
    
    h[0] = h[n + 1] = -1;
    int tt = 0;
    q[0] = 0;
    for(int i = 1; i <= n; i++){
        
        while(h[q[tt]] >= h[i]) tt--;
        l[i] = q[tt];
        q[++tt] = i;
    }
    
    tt = 0;
    q[0] = n + 1;
    for(int i = n; i >= 1; i--){
        
        while(h[q[tt]] >= h[i]) tt--;
        r[i] = q[tt];
        q[++tt] = i;
    }
    int res = 0;
    for(int i = 1; i <= n; i++)
        res = max(res, h[i] * (r[i] - l[i] - 1));
    
    return res;
}


void init(){
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++)
            if(g[i][j] == '1') s[i][j] = s[i-1][j] + 1;
            else s[i][j] = 0;
        
        U[i] = max(U[i-1], calc(s[i], m));
    }
    
    memset(s, 0, sizeof s);
    for(int i = n; i; i--){
        for(int j = 1; j <= m; j++)
            if(g[i][j] == '1') s[i][j] = s[i + 1][j] + 1; 
            else s[i][j] = 0;
        D[i] = max(D[i+1], calc(s[i], m));
    }
    
    memset(s, 0, sizeof s);
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++)
            if(g[j][i] == '1') s[i][j] = s[i - 1][j] + 1;
            else s[i][j] = 0;
        L[i] = max(L[i - 1], calc(s[i], n));
    }
    
    memset(s, 0, sizeof s);
    for(int i = m; i; i--){
        for(int j = 1; j <= n; j++)
            if(g[j][i] == '1') s[i][j] = s[i + 1][j] + 1;
            else s[i][j] = 0;
        R[i] = max(R[i + 1], calc(s[i], n));
    }
}


int main(){
    
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%s", g[i] + 1);
    
    init();
    
    int t;
    scanf("%d", &t);
    
    while(t--){
        
        int x, y;
        scanf("%d%d", &x, &y);
        
        x++, y++;
        printf("%d\n", max(max(U[x-1], D[x+1]), max(L[y-1], R[y+1])));
    }
    
    return 0;
}