Universal Cup Judging System

Universal Cup

시간 제한: 3.0 s 메모리 제한: 1024 MB 총점: 100 해킹 가능 ✓
통계

Hay un parque con $N$ plazas dispuestas en fila de izquierda a derecha, numeradas $0, 1, \dots, N - 1$ en este orden.

Dentro del parque hay $N$ personas, también numeradas $0, 1, \dots, N - 1$. Cuando anuncias una secuencia $X = (X_1, X_2, \dots, X_{|X|})$ de enteros no negativos entre $0$ y $N - 1$, las personas realizan una marcha siguiendo estas reglas:

  1. Para cada $i = 0, 1, \dots, N - 1$, la persona $i$ se mueve a la plaza $i$.
  2. Para cada $j = 1, 2, \dots, |X|$, en este orden, se hace lo siguiente:
    • Cada persona que no se encuentre actualmente en la plaza $X_j$ se mueve exactamente una plaza hacia $X_j$.

Se te da una secuencia $A = (A_0, A_1, \dots, A_{M-1})$ de longitud $M$, formada por enteros entre $0$ y $N - 1$.

Debes responder a $Q$ consultas en línea (online). Para cada $i = 1, 2, \dots, Q$, se dan los enteros $t'_i, L'_i, R'_i, P'_i$. Primero, reconstruye $t_i, L_i, R_i, P_i$ mediante el siguiente procedimiento:

Sea $\text{ans}_0 = 0$, y sea $\text{ans}_i$ la respuesta a la $i$-ésima consulta. Reconstruye $t_i, L_i, R_i, P_i$ como sigue:

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

Aquí, para un entero no negativo $a$ y un entero positivo $b$, $(a \bmod b)$ denota el resto de dividir $a$ entre $b$, que está en el rango de $0$ a $b - 1$.

Para cada $(t_i, L_i, R_i, P_i)$ reconstruido, responde a la siguiente consulta:

  • Si $t_i = 0$: Sea $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simula la marcha e imprime la plaza final en la que termina la persona $P_i$.
  • Si $t_i = 1$: Sea $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Simula la marcha e imprime cuántas personas terminan en la plaza $P_i$.

Entrada

La entrada se proporciona en el siguiente formato:

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
  • Todos los valores de entrada son enteros.
  • $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$)

Salida

Imprime $Q$ líneas. Para cada $i = 1, 2, \dots, Q$, imprime $\text{ans}_i$, la respuesta a la $i$-ésima consulta.

Ejemplos

Entrada de ejemplo 1

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

Salida de ejemplo 1

2
0
3

Entrada de ejemplo 2

7 4 1
3 3 3 3
1 3 0 3

Salida de ejemplo 2

7

Nota

En la primera consulta del ejemplo 1, para $(t_i, L_i, R_i, P_i) = (0, 1, 3, 2)$ con $X = (2, 3, 2)$, la persona $2$ se mueve como $2 \to 2 \to 3 \to 2$, por lo que la respuesta es $2$.

En la segunda consulta del ejemplo 1, para $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$ con $X = (3, 2, 1)$, el número de personas en la plaza $3$ al final es $0$.

En la tercera consulta del ejemplo 1, para $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$ con $X = (1)$, el número de personas en la plaza $1$ al final es $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.