Universal Cup Judging System

Universal Cup

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

Є парк із $N$ площами, розташованими в ряд зліва направо та пронумерованими в цьому порядку числами $0, 1, \dots, N - 1$.

У парку перебувають $N$ людей, також пронумерованих числами $0, 1, \dots, N - 1$. Коли ви оголошуєте послідовність $X = (X_1, X_2, \dots, X_{|X|})$ із невід'ємних цілих чисел від $0$ до $N - 1$, люди здійснюють ходу за такими правилами:

  1. Для кожного $i = 0, 1, \dots, N - 1$ людина $i$ переходить на площу $i$.
  2. Для кожного $j = 1, 2, \dots, |X|$ у цьому порядку виконується таке:
    • Кожна людина, яка зараз не перебуває на площі $X_j$, переміщується рівно на одну площу в напрямку площі $X_j$.

Вам дано послідовність $A = (A_0, A_1, \dots, A_{M-1})$ довжини $M$, що складається з цілих чисел від $0$ до $N - 1$.

Ви повинні відповісти на $Q$ онлайн-запитів. Для кожного $i = 1, 2, \dots, Q$ задано цілі числа $t'_i, L'_i, R'_i, P'_i$. Спочатку відновіть $t_i, L_i, R_i, P_i$ за допомогою такої процедури:

Нехай $\text{ans}_0 = 0$, а $\text{ans}_i$ позначає відповідь на $i$-й запит. Відновіть $t_i, L_i, R_i, P_i$ таким чином:

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

Тут для невід'ємного цілого числа $a$ та додатного цілого числа $b$ вираз $(a \bmod b)$ позначає остачу від ділення $a$ на $b$, яка лежить у діапазоні від $0$ до $b - 1$.

Для кожної відновленої четвірки $(t_i, L_i, R_i, P_i)$ дайте відповідь на такий запит:

  • Якщо $t_i = 0$: Нехай $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Промоделюйте ходу та виведіть кінцеву площу, на якій опиниться людина $P_i$.
  • Якщо $t_i = 1$: Нехай $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$. Промоделюйте ходу та виведіть, скільки людей у результаті опиниться на площі $P_i$.

Вхідні дані

Вхідні дані подано в такому форматі:

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
  • Усі вхідні значення є цілими числами.
  • $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$)

Вихідні дані

Виведіть $Q$ рядків. Для кожного $i = 1, 2, \dots, Q$ виведіть $\text{ans}_i$ — відповідь на $i$-й запит.

Приклади

Приклад вводу 1

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

Приклад виводу 1

2
0
3

Приклад вводу 2

7 4 1
3 3 3 3
1 3 0 3

Приклад виводу 2

7

Примітка

У першому запиті прикладу 1 для $(t_i, L_i, R_i, P_i) = (0, 1, 3, 2)$ з $X = (2, 3, 2)$ людина $2$ рухається як $2 \to 2 \to 3 \to 2$, тому відповідь дорівнює $2$.

У другому запиті прикладу 1 для $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$ з $X = (3, 2, 1)$ кількість людей на площі $3$ наприкінці дорівнює $0$.

У третьому запиті прикладу 1 для $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$ з $X = (1)$ кількість людей на площі $1$ наприкінці дорівнює $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.