7 . 對號鹿座

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

iantsai

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

72.7% (8/11)

Tags

ntucpc-challenge1

Description


日野南高校入學典禮，由學生會長虎視虎子向新生致詞

為了入學典禮的能流暢地進行，充分的事前準備也是不能少的，其中一個重點準備項目便是新生們的入場。

會場的座位一共有 $N$ 個橫行及 $M$ 個直列，形成一個 $N \times M$ 的二維表格，每個座位恰有一位學生。為了確保入場時人流順暢，校方將學生以 $1$ 到 $N \times M$ 的整數編號，事先安排好每位學生的座位，並讓學生們分批進入會場。所有學生被分成 $K$ 個梯次，第 $i$ 個梯次將由編號最小的還沒進場的前 $s_i$ 名學生進入會場。進入會場後學生便會前往自己的座位，待所有學生皆就座後，再開放下一個梯次的學生進入會場，直到 $K$ 個梯次結束，$N \times M$ 位學生皆入場為止。

不過只有井然有序的入場順序還不夠，座位編號的規畫也是相當重要的。為了確保新入場的學生不要被已經入座的學生阻擋到去路，在每一個梯次的學生全部入座後，所有已經入場的學生的座位分布都會滿足以下的條件：所有已就座的學生四方位連通，且此連通塊為滿足「曼哈頓凸」的性質。

所謂「曼哈頓凸」的性質直觀地形容便是連通塊中沒有凹槽或空洞。嚴謹的說，一個二維表格上的連通塊滿足「曼哈頓凸」的性質若且唯若連通塊中的任兩個點它們在連通塊中的最短距離即為兩個點之間的曼哈頓距離。

看到新生入學的虎視虎子感到很懷念，便回憶起當年她新入學時入學典禮的座位表。雖然鹿乃子乃子是轉學生，不過她很好奇當年虎視虎子的入學典禮的樣貌。雖然正確的數字已不可考，但鹿乃子乃子想請你寫一支程式幫她算一算，根據上述的座位安排方式，學生最多是被分成幾個梯次進場的。

另外，由於兩年前的記憶已經模糊，虎視虎子可能會突然回想起一些細節，並交換座位表上其中兩個位置的編號。每次回想後的修改是會累積的，也就是說每次交換完兩個編號後，在下一次回想前並不會將兩個編號換回去。

Input Format

輸入的第一行包含兩個整數 $N, M$。接下來 $N$ 行，第 $i$ 行包含 $M$ 個整數 $a_{i,j}$，表示第 $i$ 行第 $j$ 列的座位的學生編號。下一行為一整數 $Q$，表示虎視虎子回想起的細節。接下來 $Q$ 行，每行包含四個整數 $r_1, c_1, r_2, c_2$，表示交換座位表第 $r_1$ 行第 $c_1$ 列與第 $r_2$ 行第 $c_2$ 列的編號。

  • $1 \le N$
  • $1 \le M$
  • $1 \le N \times M \le 10^ 5$
  • $1 \le a_{i,j} \le N \times M$
  • $a_{i_1,j_1} \ne a_{i_2,j_2}, \forall (i_1,j_1) \ne (i_2,j_2)$
  • $0 \le Q \le 10^ 5$
  • 對於每一個回想起的細節：
    • $1 \le r_1, r_2 \le N$
    • $1 \le c_1, c_2 \le M$
    • $(r_1,c_1) \ne (r_2,c_2)$

Output Format

第一行請輸出一個整數，表示透過原本的座位表推論出的最多可能被分成的梯次。接下來 $Q$ 行，第 $i$ 行請輸出一個整數，表示經過前 $i$ 次回想後修改的座位表推論出的最多可能被分成的梯次。

Sample Input 1

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

Sample Output 1

6
2
2
6

Sample Input 2

1 6
5 3 1 2 4 6
5
1 3 1 5
1 1 1 2
1 2 1 4
1 3 1 5
1 4 1 6

Sample Output 2

6
5
4
3
5
4

Hints

第一筆範例測資，一開始的座位表最多可以被分為 $K=6$ 梯次，每個梯次進場的學生數量依序為 $s_i = [1, 1, 1, 1, 1, 4]$。接下來每次回想後修改的結果如下：

  • 經過第一次的回想後，最多可以被分為 $K=2$ 梯次，各梯次的學生數量為 $s_i = [1,8]$。
  • 經過前兩次的回想後，最多可以被分為 $K=2$ 梯次，各梯次的學生數量為 $s_i = [1,8]$。
  • 經過前三次的回想後，最多可以被分為 $K=6$ 梯次，各梯次的學生數量為 $s_i = [1,2,1,1,1,3]$。

Problem Source

改編自 IOI 2018 Day 1 p2 - Seats

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資。 0
2 0~23 $N\times M \leq 100, Q\leq 100$。 1
3 24~41 $N=1$。 9
4 42~79 $Q=0$。 30
5 0~116 無特別限制。 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 6000 1048576 65536 1 2 5
1 6000 1048576 65536 1 2 5
2 6000 1048576 65536 2 5
3 6000 1048576 65536 2 5
4 6000 1048576 65536 2 5
5 6000 1048576 65536 2 5
6 6000 1048576 65536 2 5
7 6000 1048576 65536 2 5
8 6000 1048576 65536 2 5
9 6000 1048576 65536 2 5
10 6000 1048576 65536 2 5
11 6000 1048576 65536 2 5
12 6000 1048576 65536 2 5
13 6000 1048576 65536 2 5
14 6000 1048576 65536 2 5
15 6000 1048576 65536 2 5
16 6000 1048576 65536 2 5
17 6000 1048576 65536 2 5
18 6000 1048576 65536 2 5
19 6000 1048576 65536 2 5
20 6000 1048576 65536 2 5
21 6000 1048576 65536 2 5
22 6000 1048576 65536 2 5
23 6000 1048576 65536 2 5
24 6000 1048576 65536 3 5
25 6000 1048576 65536 3 5
26 6000 1048576 65536 3 5
27 6000 1048576 65536 3 5
28 6000 1048576 65536 3 5
29 6000 1048576 65536 3 5
30 6000 1048576 65536 3 5
31 6000 1048576 65536 3 5
32 6000 1048576 65536 3 5
33 6000 1048576 65536 3 5
34 6000 1048576 65536 3 5
35 6000 1048576 65536 3 5
36 6000 1048576 65536 3 5
37 6000 1048576 65536 3 5
38 6000 1048576 65536 3 5
39 6000 1048576 65536 3 5
40 6000 1048576 65536 3 5
41 6000 1048576 65536 3 5
42 6000 1048576 65536 4 5
43 6000 1048576 65536 4 5
44 6000 1048576 65536 4 5
45 6000 1048576 65536 4 5
46 6000 1048576 65536 4 5
47 6000 1048576 65536 4 5
48 6000 1048576 65536 4 5
49 6000 1048576 65536 4 5
50 6000 1048576 65536 4 5
51 6000 1048576 65536 4 5
52 6000 1048576 65536 4 5
53 6000 1048576 65536 4 5
54 6000 1048576 65536 4 5
55 6000 1048576 65536 4 5
56 6000 1048576 65536 4 5
57 6000 1048576 65536 4 5
58 6000 1048576 65536 4 5
59 6000 1048576 65536 4 5
60 6000 1048576 65536 4 5
61 6000 1048576 65536 4 5
62 6000 1048576 65536 4 5
63 6000 1048576 65536 4 5
64 6000 1048576 65536 4 5
65 6000 1048576 65536 4 5
66 6000 1048576 65536 4 5
67 6000 1048576 65536 4 5
68 6000 1048576 65536 4 5
69 6000 1048576 65536 4 5
70 6000 1048576 65536 4 5
71 6000 1048576 65536 4 5
72 6000 1048576 65536 4 5
73 6000 1048576 65536 4 5
74 6000 1048576 65536 4 5
75 6000 1048576 65536 4 5
76 6000 1048576 65536 4 5
77 6000 1048576 65536 4 5
78 6000 1048576 65536 4 5
79 6000 1048576 65536 4 5
80 6000 1048576 65536 5
81 6000 1048576 65536 5
82 6000 1048576 65536 5
83 6000 1048576 65536 5
84 6000 1048576 65536 5
85 6000 1048576 65536 5
86 6000 1048576 65536 5
87 6000 1048576 65536 5
88 6000 1048576 65536 5
89 6000 1048576 65536 5
90 6000 1048576 65536 5
91 6000 1048576 65536 5
92 6000 1048576 65536 5
93 6000 1048576 65536 5
94 6000 1048576 65536 5
95 6000 1048576 65536 5
96 6000 1048576 65536 5
97 6000 1048576 65536 5
98 6000 1048576 65536 5
99 6000 1048576 65536 5
100 6000 1048576 65536 5
101 6000 1048576 65536 5
102 6000 1048576 65536 5
103 6000 1048576 65536 5
104 6000 1048576 65536 5
105 6000 1048576 65536 5
106 6000 1048576 65536 5
107 6000 1048576 65536 5
108 6000 1048576 65536 5
109 6000 1048576 65536 5
110 6000 1048576 65536 5
111 6000 1048576 65536 5
112 6000 1048576 65536 5
113 6000 1048576 65536 5
114 6000 1048576 65536 5
115 6000 1048576 65536 5
116 6000 1048576 65536 5
Submit
Back to Top