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

给定一个 $N\times M$ 的 $01$ 矩阵，矩阵下标从 $0$ 开始。

有 $Q$ 个询问，第 $i$ 个询问为：将矩阵中 ($x_i,y_i$) 的元素改成 $0$ 之后，只包含 $1$ 的子矩阵的最大面积是多少。

注意：

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

输入格式
第一行包含两个整数 $N,M$。

接下来 $N$ 行，每行包含 $M$ 个 $01$ 字符。

再一行包含整数 $Q$。

接下来 $Q$ 行，每行包含 $2$ 个整数 ($x_i,y_i$)。

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

数据范围
对于 20% 的数据，$1\le N,M,Q\le 10$
对于 50% 的数据，$1\le N,M,Q\le 100$
对于 100% 的数据，$1\le N,M\le 2000,1\le Q\le 10^5,0\le x_i<n,0\le y_i<m$
输入样例：

4 2
10
11
11
11
3
0 0
2 0
3 1
1
2
3
4
5
6
7
8
9

输出样例：

6
3
4
1
2
3

---

#include
#include

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98