CF 433D 题解
SkyRainWind
·
·
题解
题意：
七海千秋和日向创在玩游戏。抽象来说是这么一个问题：
一个 n \times m 的矩阵，每个元素都是 0/1，有 q 个操作，每个操作形如 op,x,y ，如果 op 为 1 ，就将 (x,y) 的 0/1 值取反，如果 op 为 2 ，就查询 (x,y) 所在的全为 1 的矩阵中最大的面积（当然 (x,y) 本身也得是 1 ），其中 (x,y) 这个点是该矩阵四条边上的一个点。
题解：
这套题浓度爆表啊。。不然我还真不一定能做下去。
查询的时候就向右扫，记一个 $min_1$ 表示向上的最小长度，$min_2$ 表示向下的，然后当前位置 $(i,y)$ 的贡献就是 $(y-j+1) \times (min_1+min_2-1)$ 。
同理维护其它的即可，代码会有很多重复的部分，一定要仔细。我少复制了一句话调了1h+。
```cpp
// LUOGU_RID: 94164894
// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>
using namespace std;
typedef long long LL;
const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 1005;
int n,m,q,a[maxn][maxn],ut[maxn][maxn][4]; // 0 left 1 right 2 up 3 down
signed main(){
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;){
if(a[i][j] == 0){
ut[i][j][0] = 0;
++ j;
continue;
}
int cnt = 0;
while(a[i][j]){
ut[i][j][0] = ++ cnt;
++ j;
}
}
for(int j=m;j>=1;){
if(a[i][j] == 0){
ut[i][j][1] = 0;
-- j;
continue;
}
int cnt = 0;
while(a[i][j]){
ut[i][j][1] = ++ cnt;
-- j;
}
}
}
for(int j=1;j<=m;j++){
for(int i=1;i<=n;){
if(a[i][j] == 0){
ut[i][j][2] = 0;
i ++;continue;
}
int cnt = 0;
while(a[i][j] == 1){
ut[i][j][2] = ++ cnt;
++ i;
}
}
for(int i=n;i>=1;){
if(a[i][j] == 0){
ut[i][j][3] = 0;
i --;continue;
}
int cnt = 0;
while(a[i][j] == 1){
ut[i][j][3] = ++ cnt;
-- i;
}
}
}
while(q --){
int op,x,y;scanf("%d%d%d",&op,&x,&y);
if(op == 2){
if(a[x][y] == 0){
puts("0");
continue;
}
// 0 left 1 right 2 up 3 down
int ans = ut[x][y][2] + ut[x][y][3] - 1;
int mn1=ut[x][y][2], mn2 = ut[x][y][3];
for(int i=y+1;i<=y+ut[x][y][1]-1;i++){
mn1 = min(mn1, ut[x][i][2]);
mn2 = min(mn2, ut[x][i][3]);
ans = max(ans, (mn1 + mn2 - 1) * (i-y+1));
} // to rightmost
mn1=ut[x][y][2], mn2 = ut[x][y][3];
for(int i=y-1;i>=y-ut[x][y][0]+1;i--){
mn1 = min(mn1, ut[x][i][2]);
mn2 = min(mn2, ut[x][i][3]);
ans = max(ans, (mn1 + mn2 - 1) * (y-i+1));
} // to leftmost
mn1=ut[x][y][0], mn2 = ut[x][y][1];
ans = max(ans, mn1 + mn2 - 1);
for(int i=x+1;i<=x+ut[x][y][3]-1;i++){
mn1 = min(ut[i][y][0], mn1);
mn2 = min(ut[i][y][1], mn2);
ans = max(ans, (mn1 + mn2 - 1) * (i-x+1));
} // to bottom
mn1 = ut[x][y][0], mn2 = ut[x][y][1];
for(int i=x-1;i>=x-ut[x][y][2]+1;i--){
mn1 = min(ut[i][y][0], mn1);
mn2 = min(ut[i][y][1], mn2);
ans = max(ans, (mn1 + mn2 - 1) * (x-i+1));
} // to top
printf("%d\n",ans);
}else{
a[x][y] ^= 1;
if(a[x][y] == 1){
ut[x][y][1] = ut[x][y+1][1] + 1;
ut[x][y][0] = ut[x][y-1][0] + 1;
ut[x][y][2] = ut[x-1][y][2] + 1;
ut[x][y][3] = ut[x+1][y][3] + 1;
}else ut[x][y][0] = ut[x][y][1] = ut[x][y][2] = ut[x][y][3] = 0;
for(int i=y-1;i>=1;i--){
if(a[x][i] == 0)break;
ut[x][i][1] = ut[x][i+1][1] + 1;
}
for(int i=y+1;i<=m;i++){
if(a[x][i] == 0)break;
ut[x][i][0] = ut[x][i-1][0] + 1;
}
for(int i=x+1;i<=n;i++){
if(a[i][y] == 0)break;
ut[i][y][2] = ut[i-1][y][2] + 1;
}
for(int i=x-1;i>=1;i--){
if(a[i][y] == 0)break;
ut[i][y][3] = ut[i+1][y][3] + 1;
}
}
}
return 0;
}
```