Universal Cup Judging System

Universal Cup

Limite de temps : 3.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

Terdapat sebuah taman dengan $N$ alun-alun yang tersusun dalam satu baris dari kiri ke kanan, dinomori $0, 1, \dots, N - 1$ sesuai urutan tersebut.

Di dalam taman, terdapat $N$ orang, yang juga dinomori $0, 1, \dots, N - 1$. Ketika Anda mengumumkan sebuah barisan $X = (X_1, X_2, \dots, X_{|X|})$ yang terdiri dari bilangan-bilangan bulat tak negatif antara $0$ dan $N - 1$, orang-orang tersebut melakukan baris-berbaris sesuai aturan berikut:

  1. Untuk setiap $i = 0, 1, \dots, N - 1$, orang $i$ berpindah ke alun-alun $i$.
  2. Untuk setiap $j = 1, 2, \dots, |X|$, sesuai urutan ini, lakukan hal berikut:
    • Setiap orang yang saat ini tidak berada di alun-alun $X_j$ bergerak tepat satu alun-alun mendekati $X_j$.

Anda diberikan sebuah barisan $A = (A_0, A_1, \dots, A_{M-1})$ sepanjang $M$, yang terdiri dari bilangan-bilangan bulat antara $0$ dan $N - 1$.

Anda harus menjawab $Q$ kueri daring (online). Untuk setiap $i = 1, 2, \dots, Q$, diberikan bilangan-bilangan bulat $t'_i, L'_i, R'_i, P'_i$. Pertama, rekonstruksi $t_i, L_i, R_i, P_i$ menggunakan prosedur berikut:

Misalkan $\text{ans}_0 = 0$, dan misalkan $\text{ans}_i$ menyatakan jawaban untuk kueri ke-$i$. Rekonstruksi $t_i, L_i, R_i, P_i$ sebagai berikut:

  • $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)$

Di sini, untuk bilangan bulat tak negatif $a$ dan bilangan bulat positif $b$, $(a \bmod b)$ menyatakan sisa pembagian ketika $a$ dibagi dengan $b$, yang berada dalam rentang $0$ hingga $b - 1$.

Untuk setiap $(t_i, L_i, R_i, P_i)$ yang telah direkonstruksi, jawablah kueri berikut:

  • Jika $t_i = 0$: Misalkan $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simulasikan baris-berbaris tersebut dan keluarkan alun-alun akhir tempat orang $P_i$ berada.
  • Jika $t_i = 1$: Misalkan $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simulasikan baris-berbaris tersebut dan keluarkan berapa banyak orang yang berakhir di alun-alun $P_i$.

Masukan

Masukan diberikan dalam format berikut:

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
  • Semua nilai masukan adalah bilangan bulat.
  • $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$)

Keluaran

Keluarkan $Q$ baris. Untuk setiap $i = 1, 2, \dots, Q$, keluarkan $\text{ans}_i$, yaitu jawaban untuk kueri ke-$i$.

Contoh

Contoh Masukan 1

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

Contoh Keluaran 1

2
0
3

Contoh Masukan 2

7 4 1
3 3 3 3
1 3 0 3

Contoh Keluaran 2

7

Catatan

Pada kueri pertama Contoh 1, untuk $(t_i, L_i, R_i, P_i) = (0, 1, 3, 2)$ dengan $X = (2, 3, 2)$, orang $2$ bergerak sebagai $2 \to 2 \to 3 \to 2$, sehingga jawabannya adalah $2$.

Pada kueri kedua Contoh 1, untuk $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$ dengan $X = (3, 2, 1)$, banyaknya orang di alun-alun $3$ pada akhirnya adalah $0$.

Pada kueri ketiga Contoh 1, untuk $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$ dengan $X = (1)$, banyaknya orang di alun-alun $1$ pada akhirnya adalah $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.