Server Time:

User's AC Ratio in this contest

0.0% (0/8)

Submission's AC Ratio in this contest

0.0% (0/27)

Description

給你一個 $N\times M$ 的方格紙,
一開始方格紙上面有些格子是黑色,有些格子是白色。
接著會有 $Q$ 筆操作,每次操作將一個白色格子塗黑,
每一筆操作為相依的,
也就是說你塗完一個格子後下次操作也不會恢復原狀。
請問每次操作後會有多少白色格子的聯通塊,
以及最大塊白色聯通塊的大小為何?

如果兩個格子有一個共同邊且顏色相同,
則我們視這兩個格子為聯通,
如果找到一塊極大數量且聯通的格子,則稱為聯通塊。
如下圖有三個聯通塊。

Input Format

第一行有三個正整數 $N,M,Q$,代表方格紙的大小為 $N\times M$,並且有 $Q$ 筆詢問。
接下來 $N$ 行, 每行有 $M$ 個數字 $a$,代表方格紙一開始的狀態,若 $a$ 為 $0$ 代表該格子為白色,若 $a$ 為 $1$ 則代表該格子為黑色。
接下來 $Q$ 行,每行有兩個正整數 $r,c$,代表要將格子 $(r,c)$ 塗成黑色。

  • $1\leq N,M\leq3000$
  • $Q\leq2\times10^5$
  • $a\in{0,1}$
  • $1\leq r\leq N$
  • $1\leq c\leq M$

Output Format

對於每一筆操作,請輸出兩個數字,分別代表白色格子的聯通塊數量及最大的白色聯通塊大小。

Sample Input 1

5 8 5
0 1 0 0 0 0 1 0
0 1 0 0 0 0 1 0
0 0 1 1 1 0 0 1
0 0 0 1 0 0 1 0
0 0 0 1 0 0 0 0
3 1
1 8
3 6
1 3
3 7

Sample Output 1

4 17
4 17
6 8
6 7
5 7

Sample Input 2

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

Sample Output 2

4 26
4 25
4 24
5 21
5 20
6 10
7 9
7 8

Hints

此為 Sample Testcase 1 的圖形

Problem Source

Subtasks

No. Testdata Range Score
1 0~37 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3000 196608 65536 1
1 3000 196608 65536 1
2 3000 196608 65536 1
3 3000 196608 65536 1
4 3000 196608 65536 1
5 3000 196608 65536 1
6 3000 196608 65536 1
7 3000 196608 65536 1
8 3000 196608 65536 1
9 3000 196608 65536 1
10 3000 196608 65536 1
11 3000 196608 65536 1
12 3000 196608 65536 1
13 3000 196608 65536 1
14 3000 196608 65536 1
15 3000 196608 65536 1
16 3000 196608 65536 1
17 3000 196608 65536 1
18 3000 196608 65536 1
19 3000 196608 65536 1
20 3000 196608 65536 1
21 3000 196608 65536 1
22 3000 196608 65536 1
23 3000 196608 65536 1
24 3000 196608 65536 1
25 3000 196608 65536 1
26 3000 196608 65536 1
27 3000 196608 65536 1
28 3000 196608 65536 1
29 3000 196608 65536 1
30 3000 196608 65536 1
31 3000 196608 65536 1
32 3000 196608 65536 1
33 3000 196608 65536 1
34 3000 196608 65536 1
35 3000 196608 65536 1
36 3000 196608 65536 1
37 3000 196608 65536 1