Universal Cup Judging System

Universal Cup

Límite de tiempo: 3.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

Có một công viên gồm $N$ quảng trường được xếp thành một hàng từ trái sang phải, được đánh số $0, 1, \dots, N - 1$ theo thứ tự đó.

Bên trong công viên có $N$ người, cũng được đánh số $0, 1, \dots, N - 1$. Khi bạn công bố một dãy $X = (X_1, X_2, \dots, X_{|X|})$ gồm các số nguyên không âm nằm giữa $0$ và $N - 1$, mọi người sẽ thực hiện một cuộc diễu hành theo các quy tắc sau:

  1. Với mỗi $i = 0, 1, \dots, N - 1$, người thứ $i$ di chuyển đến quảng trường $i$.
  2. Với mỗi $j = 1, 2, \dots, |X|$, theo thứ tự này, thực hiện điều sau:
    • Mỗi người hiện không ở tại quảng trường $X_j$ sẽ di chuyển đúng một quảng trường về phía $X_j$.

Bạn được cho một dãy $A = (A_0, A_1, \dots, A_{M-1})$ có độ dài $M$, gồm các số nguyên nằm giữa $0$ và $N - 1$.

Bạn phải trả lời $Q$ truy vấn trực tuyến (online). Với mỗi $i = 1, 2, \dots, Q$, các số nguyên $t'_i, L'_i, R'_i, P'_i$ được cho trước. Trước tiên, hãy khôi phục $t_i, L_i, R_i, P_i$ bằng quy trình sau:

Đặt $\text{ans}_0 = 0$, và gọi $\text{ans}_i$ là câu trả lời cho truy vấn thứ $i$. Khôi phục $t_i, L_i, R_i, P_i$ như sau:

  • $t_i = ((t'_i + \text{ans}_{i-1}) \bmod 2)$
  • $a = ((L'_i + \text{ans}_{i-1}) \bmod M)$
  • $b = ((R'_i + \text{ans}_{i-1}) \bmod M)$
  • $L_i = \min(a, b)$
  • $R_i = \max(a, b)$
  • $P_i = ((P'_i + \text{ans}_{i-1}) \bmod N)$

Ở đây, với số nguyên không âm $a$ và số nguyên dương $b$, $(a \bmod b)$ biểu thị số dư khi chia $a$ cho $b$, nằm trong đoạn từ $0$ đến $b - 1$.

Với mỗi bộ $(t_i, L_i, R_i, P_i)$ đã khôi phục, hãy trả lời truy vấn sau:

  • Nếu $t_i = 0$: Đặt $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Hãy mô phỏng cuộc diễu hành và in ra quảng trường cuối cùng mà người $P_i$ dừng lại.
  • Nếu $t_i = 1$: Đặt $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Hãy mô phỏng cuộc diễu hành và in ra số lượng người kết thúc tại quảng trường $P_i$.

Dữ liệu vào

Dữ liệu vào được cho dưới định dạng sau:

N M Q
A_0 A_1 ... A_{M-1}
t'_1 L'_1 R'_1 P'_1
t'_2 L'_2 R'_2 P'_2
:
t'_Q L'_Q R'_Q P'_Q
  • Tất cả các giá trị đầu vào đều là số nguyên.
  • $1 \le N, M, Q \le 2 \times 10^5$
  • $0 \le A_i \le N - 1$ ($0 \le i \le M - 1$)
  • $0 \le t'_i, t_i \le 1$ ($1 \le i \le Q$)
  • $0 \le L'_i, R'_i \le M - 1$ ($1 \le i \le Q$)
  • $0 \le L_i \le R_i \le M - 1$ ($1 \le i \le Q$)
  • $0 \le P'_i, P_i \le N - 1$ ($1 \le i \le Q$)

Kết quả

In ra $Q$ dòng. Với mỗi $i = 1, 2, \dots, Q$, in ra $\text{ans}_i$, là câu trả lời cho truy vấn thứ $i$.

Ví dụ

Dữ liệu vào mẫu 1

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

Kết quả mẫu 1

2
0
3

Dữ liệu vào mẫu 2

7 4 1
3 3 3 3
1 3 0 3

Kết quả mẫu 2

7

Ghi chú

Ở truy vấn thứ nhất của Ví dụ 1, với $(t_i, L_i, R_i, P_i) = (0, 1, 3, 2)$ và $X = (2, 3, 2)$, người $2$ di chuyển theo lộ trình $2 \to 2 \to 3 \to 2$, nên câu trả lời là $2$.

Ở truy vấn thứ hai của Ví dụ 1, với $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$ và $X = (3, 2, 1)$, số người ở quảng trường $3$ vào cuối cuộc diễu hành là $0$.

Ở truy vấn thứ ba của Ví dụ 1, với $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$ và $X = (1)$, số người ở quảng trường $1$ vào cuối cuộc diễu hành là $3$.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.