Bạn đang tổ chức kỳ thi lập trình quốc tế trong một hội trường hình chữ nhật gồm \(HW\) ghế ngồi, được bố trí thành \(H\) hàng và \(W\) cột. Các hàng được đánh số từ \(0\) đến \(H-1\), các cột được đánh số từ \(0\) đến \(W-1\). Ghế ở hàng \(r\) và cột \(c\) được ký hiệu là \((r,c)\). Bạn mời \(HW\) thí sinh được đánh số từ \(0\) đến \(HW-1\). Bạn tạo ra sơ đồ chỗ ngồi, xếp thí sinh \(i\) (\(0 \le i \le HW-1\)) vào ghế \((R_i,C_i)\). Trong sơ đồ chỗ ngồi, mỗi thí sinh ngồi ở đúng một ghế và mỗi ghế có đúng một thí sinh.

Một tập hợp \(S\) các ghế trong hội trường được gọi là có dạng hình chữ nhật nếu tồn tại các số nguyên \(r_1\), \(r_2\), \(c_1\) và \(c_2\) thỏa mãn các điều kiện sau:

• \(0 \le r_1 \le r_2 \le H-1\).
• \(0 \le c_1 \le c_2 \le W-1\).
• \(S\) chính là tập hợp tất cả các ghế \((r,c)\) thỏa mãn \(r_1 \le r \le r_2\) và \(c_1 \le c \le c_2\).

Một tập hợp có dạng hình chữ nhật gồm \(k\) ghế (\(1 \le k \le HW\)) được gọi là đẹp nếu các thí sinh ngồi trên các ghế thuộc tập này có số thứ tự từ \(0\) đến \(k-1\). Độ đẹp của một sơ đồ chỗ ngồi là số lượng các tập hợp có dạng hình chữ nhật đẹp trong sơ đồ.

Sau khi tạo ra sơ đồ chỗ ngồi, bạn nhận được một số yêu cầu hoán chuyển ghế ngồi của hai thí sinh. Có \(Q\) yêu cầu, đánh số từ \(0\) đến \(Q-1\) theo thứ tự thời điểm xuất hiện. Yêu cầu \(j\) (\(0 \le j \le Q-1\)) thực hiện việc hoán chuyển chỗ ngồi của hai thí sinh \(A_j\) và \(B_j\). Bạn thực hiện ngay mỗi yêu cầu và cập nhật sơ đồ chỗ ngồi. Sau mỗi lần cập nhật, bạn cần tính độ đẹp của sơ đồ chỗ ngồi hiện tại.

Chi tiết cài đặt

Bạn phải cài đặt thủ tục và hàm sau:

give_initial_chart(int H, int W, int[] R, int[] C)

• H, W: số lượng hàng và số lượng cột.
• R, C: các mảng có độ dài \(HW\), biểu diễn sơ đồ chỗ ngồi ban đầu.
• Thủ tục này được gọi đúng một lần và trước mọi lần gọi swap_seats.

int swap_seats(int a, int b)

• Hàm này mô tả một yêu cầu hoán chuyển hai ghế ngồi.
• a, b: số thứ tự của hai thí sinh có chỗ ngồi bị hoán chuyển.
• Hàm này được gọi \(Q\) lần.
• Hàm này phải trả về độ đẹp của sơ đồ chỗ ngồi sau khi thực hiện hoán chuyển.

Trong C++, giao diện trong tệp seats.h của gói đính kèm là:

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C);
int swap_seats(int a, int b);

Ví dụ

Giả sử \(H=2\), \(W=3\), \(R=[0,1,1,0,0,1]\), \(C=[0,0,1,1,2,2]\) và \(Q=2\).

Trình chấm đầu tiên gọi give_initial_chart(2, 3, [0, 1, 1, 0, 0, 1], [0, 0, 1, 1, 2, 2]).

Sơ đồ chỗ ngồi ban đầu như sau; mỗi ô ghi số thứ tự của thí sinh ngồi ở ghế đó.

Giả sử trình chấm gọi swap_seats(0, 5). Sau khi thực hiện yêu cầu \(0\), sơ đồ chỗ ngồi như sau:

Các tập hợp ghế tương ứng với các thí sinh \(\{0\}\), \(\{0,1,2\}\) và \(\{0,1,2,3,4,5\}\) có dạng hình chữ nhật và đẹp. Do đó, độ đẹp của sơ đồ chỗ ngồi là \(3\), và swap_seats phải trả lại \(3\).

Giả sử trình chấm lại gọi swap_seats(0, 5). Sau khi thực hiện yêu cầu \(1\), sơ đồ chỗ ngồi trở về trạng thái ban đầu. Các tập hợp ghế tương ứng với các thí sinh \(\{0\}\), \(\{0,1\}\), \(\{0,1,2,3\}\) và \(\{0,1,2,3,4,5\}\) có dạng hình chữ nhật và đẹp. Do đó, độ đẹp của sơ đồ chỗ ngồi này là \(4\), và swap_seats phải trả lại \(4\).

Hai tệp sample-01-in.txt và sample-01-out.txt trong gói zip đính kèm tương ứng với ví dụ này. Các ví dụ dữ liệu vào/ra khác cũng nằm trong gói này.

Hạn chế

• \(1 \le H\).
• \(1 \le W\).
• \(HW \le 1\,000\,000\).
• \(0 \le R_i \le H-1\) với \(0 \le i \le HW-1\).
• \(0 \le C_i \le W-1\) với \(0 \le i \le HW-1\).
• \((R_i,C_i) \ne (R_j,C_j)\) với \(0 \le i < j \le HW-1\).
• \(1 \le Q \le 50\,000\).
• \(0 \le a \le HW-1\) cho mọi lần gọi swap_seats.
• \(0 \le b \le HW-1\) cho mọi lần gọi swap_seats.
• \(a \ne b\) cho mọi lần gọi swap_seats.

Phân nhóm

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo khuôn dạng sau:

• Dòng \(1\): \(H\ W\ Q\).
• Dòng \(2+i\) (\(0 \le i \le HW-1\)): \(R_i\ C_i\).
• Dòng \(2+HW+j\) (\(0 \le j \le Q-1\)): \(A_j\ B_j\).

Ở đây, \(A_j\) và \(B_j\) là các tham số khi gọi swap_seats đối với yêu cầu \(j\).

Trình chấm mẫu in ra câu trả lời của bạn theo khuôn dạng sau:

• Dòng \(1+j\) (\(0 \le j \le Q-1\)): giá trị trả về của swap_seats đối với yêu cầu \(j\).

Dữ liệu vào của ví dụ trên:

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

Dữ liệu ra tương ứng:

3
4