Giáo sư X vừa giới thiệu phát minh mới nhất của mình: máy hoán đổi hạt tối thượng (UBS). Máy làm cho một dãy hạt trở nên thú vị hơn bằng cách đổi chỗ một số hạt!

UBS có \(N\) băng chuyền song song theo hướng bắc–nam, được đánh số từ \(1\) đến \(N\) từ trái sang phải. Tất cả băng chuyền chuyển động từ bắc xuống nam với cùng tốc độ. Có \(M\) bộ hoán đổi, mỗi bộ nằm giữa hai băng chuyền kề nhau. Không có hai bộ hoán đổi nào cách đầu phía bắc của máy một khoảng bằng nhau. Các bộ hoán đổi được đánh số từ \(1\) đến \(M\) theo thứ tự từ bắc xuống nam.

Để sử dụng máy, người ta đồng thời đặt \(N\) hạt tại đầu phía bắc, mỗi băng chuyền một hạt. Các hạt tạo thành một hàng ngang trong suốt quá trình chuyển động. Khi hai hạt đi tới một bộ hoán đổi, hạt trên băng chuyền bên phải được chuyển sang băng chuyền bên trái và ngược lại. Sau khi đổi chỗ, các hạt vẫn nằm trên cùng một hàng ngang. Chẳng hạn, nếu bốn hạt đang lần lượt ở trên bốn băng chuyền và bộ hoán đổi nối băng chuyền \(2\) với \(3\), thứ tự các hạt sau khi đi qua là \(1,3,2,4\).

Cho cấu hình của máy, hãy trả lời các câu hỏi: hạt được đặt ban đầu trên băng chuyền \(K\) sẽ ở trên băng chuyền nào ngay sau khi hàng hạt đi qua bộ hoán đổi \(J\)?

Giao diện lập trình

Trên LQDOJ, giao diện thư viện tương tác của đề gốc được chuyển thành giao diện hàm tương đương dưới đây. Bạn nộp mã nguồn C++ (khuyến nghị C++17), chứa #include "beads.h", cài đặt hai hàm sau và không viết hàm main:

void init(int N, int M, std::vector<int> P);
int ask(int K, int J);

Hàm init được bộ chấm gọi đúng một lần, trước mọi lời gọi ask. Hai tham số \(N,M\) lần lượt là số băng chuyền và số bộ hoán đổi. Vectơ P có \(M\) phần tử; với \(0\le i<M\), bộ hoán đổi số \(i+1\) nối băng chuyền P[i] và P[i]+1.

Sau đó, bộ chấm gọi ask đúng \(Q\) lần. Mỗi lời gọi cung cấp một câu hỏi \((K,J)\); hàm phải trả về số hiệu băng chuyền chứa hạt đó ngay sau bộ hoán đổi \(J\). Bạn phải trả lời câu hỏi hiện tại trước khi nhận câu hỏi tiếp theo. Không được đọc trước các câu hỏi, tự đọc dữ liệu vào hoặc tự ghi kết quả ra. Các câu hỏi không nhất thiết theo thứ tự tăng dần của \(J\).

Nội dung cần thiết của beads.h chính là hai khai báo hàm trong khối mã trên; hệ thống tự ghép tệp này và grader.cpp với mã nguồn của bạn khi chấm.

Dữ liệu vào

Định dạng dữ liệu dành cho bộ chấm thử:

• Dòng đầu chứa hai số nguyên \(N,M\).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa vị trí \(P_i\) của bộ hoán đổi thứ \(i\), nối băng chuyền \(P_i\) và \(P_i+1\).
• Dòng tiếp theo chứa số câu hỏi \(Q\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(K,J\) mô tả một câu hỏi.

Bộ chấm đọc cấu hình và gọi init, sau đó lần lượt đọc từng câu hỏi, gọi ask và ghi câu trả lời trước khi xử lý câu hỏi tiếp theo.

Dữ liệu ra

Bộ chấm thử ghi \(Q\) dòng, mỗi dòng là giá trị trả về của một lời gọi ask, theo thứ tự các câu hỏi.

Ràng buộc

Giới hạn thời gian: \(2\) giây. Giới hạn bộ nhớ: \(256\) MB. Một bộ dữ liệu chỉ được tính điểm khi chương trình tuân thủ giao diện và trả lời đúng tất cả câu hỏi.

Phân nhóm

Mỗi phân nhóm được chấm độc lập theo kiểu tất cả hoặc không: bạn chỉ nhận điểm của nhóm khi đúng toàn bộ test trong nhóm. Điểm trong bảng là phần điểm cộng thêm trên LQDOJ; nhóm sau bao gồm lại các test thỏa điều kiện của nhóm trước.

Ví dụ

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

1
4

Nguồn

Olympic Tin học châu Á – Thái Bình Dương 2008, bài Beads.