← 返回题目列表

Codeforces · 433/D

D. 七海的数字板

中文机器翻译题面 查看原题

七海是玩游戏的专家。这天,七海的好朋友阿一邀请她去看棒球比赛。她虽然不甘心,但还是跟着他去了体育场。不过七海对这个游戏没什么兴趣,所以她环顾四周,看看有没有什么能让她感兴趣的东西。就在那时,她看到了体育场一端的数字板。

数字板的高度为 n 个像素,宽度为 m 个像素,每个像素要么亮,要么暗。像素由其坐标来描述。第i行的第j个像素是像素(i,j)。该板通过将像素组合切换为亮,将其余像素切换为暗来显示消息。七海注意到板上像素的状态会不时发生变化。在某些时候,板上的某些像素可能会从亮变为暗,或从暗变为亮。

Nanami 想知道,特定像素位于其一侧的最大光块的面积是多少。光块是板的子矩形,其中所有像素都是光的。像素(i,j)属于以(x1,y1)和(x2,y2)为左上和右下顶点的子矩形的一条边当且仅当它满足逻辑条件:

((i = x1 或 i = x2) 和 (y1 ≤ j ≤ y2)) 或 ((j = y1 或 j = y2) 和 (x1 ≤ i ≤ x2))。

Nanami拥有更改像素的所有历史,她也有一些所描述类型的问题,你能回答吗?

输入

第一行包含三个空格分隔的整数 n、m 和 q (1 ≤ n, m, q ≤ 1000) — 数字板的高度和宽度以及操作次数。

接下来是 n 行,每行包含 m 个空格分隔的整数。第 i 行的第 j 个整数是 ai, j — 像素 (i, j) 的初始状态。

- 如果 ai, j = 0,则像素 (i, j) 最初是暗的。
- 如果 ai, j = 1,则像素 (i, j) 最初是亮的。

然后是 q 行,每行包含三个空格分隔的整数 op、x 和 y (1 ≤ op ≤ 2; 1 ≤ x ≤ n; 1 ≤ y ≤ m),描述一个操作。

- 如果 op = 1,则 (x, y) 处的像素改变其状态(从亮到暗或从暗到亮)。
- 如果 op = 2,Nanami 查询其一侧有像素 (x, y) 的最大光块。

输出

对于每个查询,打印一行包含一个整数 - Nanami 查询的答案。

示例

输入 #1

3 4 5
0 1 1 0
1 0 0 1
0 1 1 0
2 2 2
2 1 2
1 2 2
1 2 3
2 2 2

输出 #1

0
2
6

输入 #2

3 3 4
1 1 1
1 1 1
1 1 1
2 2 2
1 2 2
2 1 1
2 2 1

输出 #2

6
3
3

注意

考虑第一个样本。

第一个查询指定像素 (2, 2),该像素本身是暗的,因此没有有效的光块,因此答案为 0。

第二个查询指定像素 (1, 2)。最大的光块是左上顶点为 (1, 2) 、右下顶点为 (1, 3) 的块。

最后一个查询指定像素 (2, 2),该像素在第三次操作中变亮。最大的光块是左上顶点为 (1, 2) 、右下顶点为 (3, 3) 的块。