給你一個 $N\times M$ 的方格紙,
一開始方格紙上面有些格子是黑色,有些格子是白色。
接著會有 $Q$ 筆操作,每次操作將一個白色格子塗黑,
每一筆操作為相依的,
也就是說你塗完一個格子後下次操作也不會恢復原狀。
請問每次操作後會有多少白色格子的聯通塊,
以及最大塊白色聯通塊的大小為何?
如果兩個格子有一個共同邊且顏色相同,
則我們視這兩個格子為聯通,
如果找到一塊極大數量且聯通的格子,則稱為聯通塊。
如下圖有三個聯通塊。
第一行有三個正整數 $N,M,Q$,代表方格紙的大小為 $N\times M$,並且有 $Q$ 筆詢問。
接下來 $N$ 行, 每行有 $M$ 個數字 $a$,代表方格紙一開始的狀態,若 $a$ 為 $0$ 代表該格子為白色,若 $a$ 為 $1$ 則代表該格子為黑色。
接下來 $Q$ 行,每行有兩個正整數 $r,c$,代表要將格子 $(r,c)$ 塗成黑色。
對於每一筆操作,請輸出兩個數字,分別代表白色格子的聯通塊數量及最大的白色聯通塊大小。
此為 Sample Testcase 1 的圖形
No. | Testdata Range | Score |
---|---|---|
1 | 0~37 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 3000 | 196608 | 65536 | |
1 | 3000 | 196608 | 65536 | |
2 | 3000 | 196608 | 65536 | |
3 | 3000 | 196608 | 65536 | |
4 | 3000 | 196608 | 65536 | |
5 | 3000 | 196608 | 65536 | |
6 | 3000 | 196608 | 65536 | |
7 | 3000 | 196608 | 65536 | |
8 | 3000 | 196608 | 65536 | |
9 | 3000 | 196608 | 65536 | |
10 | 3000 | 196608 | 65536 | |
11 | 3000 | 196608 | 65536 | |
12 | 3000 | 196608 | 65536 | |
13 | 3000 | 196608 | 65536 | |
14 | 3000 | 196608 | 65536 | |
15 | 3000 | 196608 | 65536 | |
16 | 3000 | 196608 | 65536 | |
17 | 3000 | 196608 | 65536 | |
18 | 3000 | 196608 | 65536 | |
19 | 3000 | 196608 | 65536 | |
20 | 3000 | 196608 | 65536 | |
21 | 3000 | 196608 | 65536 | |
22 | 3000 | 196608 | 65536 | |
23 | 3000 | 196608 | 65536 | |
24 | 3000 | 196608 | 65536 | |
25 | 3000 | 196608 | 65536 | |
26 | 3000 | 196608 | 65536 | |
27 | 3000 | 196608 | 65536 | |
28 | 3000 | 196608 | 65536 | |
29 | 3000 | 196608 | 65536 | |
30 | 3000 | 196608 | 65536 | |
31 | 3000 | 196608 | 65536 | |
32 | 3000 | 196608 | 65536 | |
33 | 3000 | 196608 | 65536 | |
34 | 3000 | 196608 | 65536 | |
35 | 3000 | 196608 | 65536 | |
36 | 3000 | 196608 | 65536 | |
37 | 3000 | 196608 | 65536 |