Subtask 1 (33% số điểm): k, q ≤ 2000.

Subtask 2 (18% số điểm): q ≤ 30.

Ở hai \(subtask\) này, ta thực hiện mô phỏng lại yêu cầu đề bài.

Độ phức tạp: \(O(k × q)\).

Subtask 3 (27% số điểm): Không có câu hỏi loại 2.

Subtask 4 (22% số điểm): Không có ràng buộc gì thêm.

Gọi \(L(x)\) là vị trí tiếp theo của món quà đứng tại vị trí sau mỗi giây. \(R(x)\) là vị trí thỏa mãn \(L(R(x)) = x\) hay chính xác là vị trí ở giây trước của món quà ở vị trí \(x\). Vậy \(L(a_i) = −1.\)

Có \(2\) nhận xét quan trọng đầu tiên cho bài toán này:

• Với \(2\) vị trí \(x < y: R(x) < R(y), L(x) < L(y) (1).\)
• Với mỗi \(i\), gọi \(S_i\) là tập các vị trí \(a_i, R(a_i), R(R(a_i)), R(R(R(a_i))), . . .. \) ⇒ Dễ thấy tất cả các tập \(S\) đều không có phẩn tử giao. Gọi \(bel(x)\) là tập \(S_x\) mà vị trí x thuộc về. Từ đây ta thấy các tập có dạng thứ tự duy trì, và được cập nhật \(n\) lần bằng cách chèn thêm các phần tử \(a_i\) vào và tiếp tục sinh tập. (2).

Cụ thể là: nếu trước khi gặp phần tử \(a_i\), các phần tử \(x\) có \(bel(x)\) từ \(1 → i − 1\) sẽ giữ nguyên thứ tự trên vòng tròn như sau:

Nếu có các cần cẩu ở các ô 0, 2, 7, 12 thì dãy sẽ có bel như sau:

Quan sát nhỏ: Để ý i − 1 phần tử kề sau ô ai sẽ là một đoạn dịch trên cung tròn của các phần tử có bel(x) ≤ i − 1 (3).

Ví dụ: sau 2 là 1, sau 7 là 1, 2, sau 12 là 2, 3, 1.

Từ đây ta có nhiều hướng tiếp cận bài toán hiệu quả. Một hướng tiếp cận hiệu quả là chia căn: Đặt \(K = √n\), xét lần lượt các phần tử \(x: 1, K + 1, 2 × K + 1, 3 × K + 1, . . ..\) Ta tìm \(bel\) của \(x − 1\) vị trí không tính các vị trí chứa cần cẩu ngay sau \(a_x\).

Ta sẽ sử dụng kết quả của \(x\) để tìm kết quả cho \(x + K\). Dễ thấy từ \((1), (2), (3)\) thì thứ tự các phần tử có \(bel ≤ x\) sẽ giữ nguyên thứ tự trên đường tròn nên khi đi qua vị trí \(a_x+K\) vẫn sẽ giữ nguyên thứ tự đó. Nhưng ở giữa những vị trí có \(bel ≤ x\) đó sẽ được chèn giữa bởi những phần tử có \(bel > x\).

Nhưng ta có thể dễ dàng tìm được những phần tử chèn giữa vì chỉ có 2 trường hợp cho những phần tử này:

1. Những vị trí chứa cầu cẩu mới.
2. Những vị trí có \(bel\) nằm trong khoảng \(x + 1 → x + K − 1\).

Trường hợp \(1\) không cần tìm kiếm.

Trường hợp \(2\) ta xử lý đơn giản như sau: dùng những thao tác nhảy đơn giản để từ vị trí \(a_z\) tìm vị trí có \(bel = z\) đầu tiên sau vị trí \(a_x+K\). Thao tác nhảy với mỗi phần tử chỉ mất độ phức tạp là \(O(K)\) vì chỉ cần nhảy qua \(K\) cần cẩu.

Lưu ý: phải lưu lại được số bước nhảy trên mỗi thao tác để tính toán. Luôn lưu ý đích đến luôn đi cùng với số bước thao tác nhảy để tính toán. Ta sẽ tính thêm \(1\) mảng \(C_i\) là số bước mà vị trí \(a_i\) cần để nhảy tới vị trí đầu tiên có \(bel = \)i sau vị trí \(a_n\).

Lặp lại thuật toán này sẽ dễ dàng tính được các phần tử có thứ tự \(bel\) như nào trên vòng tròn.

Xử lý truy vấn:

Truy vấn \(1\) có thể xử lý đơn giản bằng cách: gọi vị trí hiện tại là \(x\), nếu \(x < a_n\) thì nhảy tới vị trí đầu tiên sau an và đếm số bước. Ngược lại nếu \(x > a_n\) thì chỉ việc nhảy tới vị trí đầu tiên sau \(a[n]\) bằng \(1\) phép toán đơn giản.

Nếu \(x < a_n\) ta sẽ nhảy bằng cách sử dụng các phép nhảy mình đã chuẩn bị trước từ đầu. Giả sử \(x\) nằm trong khoảng \([a_u, a_{u+1}]\) thì chỉ cần nhảy tới khoảng căn tiếp theo (vị trí đầu tiên sau \(a_1+r×K\) nào đó) sẽ tìm được \(bel(x)\) và đếm số bước chính là số bước nhảy tới \(bel(x)\) cộng thêm số bước từ vị trí sau \(a_1+r×K\) cần để nhảy tới vị trí đầu tiên sau \(a_n\).

Gọi số bước cần để nhảy tới vị trí sau \(a_n\) là \(num\) thì kết quả chính là \(C_{bel(x)} − num\). (với trường hợp nhảy từ \(x > a_n\) xuống mình sẽ để số bước âm).

Tương tự với truy vấn \(2\). Vì có các vùng căn nên có thể sử dụng để tính toán vị trí của \(x\) sau \(y\) bước dễ dàng bằng thuật toán nhảy \(block\) và nhảy trong \(block\). Dễ thấy thao tác nhảy \(block\) mất \(O(1)\) và nhảy trong \(block\) qua các khoảng \([a_{i−1}, a_i]\) cũng chỉ mất \(O(1)\). Điểm quan trọng là phải lưu lại được số bước nhảy giữa \(2\) \(block\) như đã nói phía trên để tính toán được kết quả.

Độ phức tạp: \(O(q × √n).\)