Universal Cup Judging System

Universal Cup

時間限制: 3.0 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓
统计

左から右へ一列に並んだ $N$ 個の広場がある公園があり、順に $0, 1, \dots, N - 1$ の番号が付けられています。

公園の中には $N$ 人の人がおり、同様に $0, 1, \dots, N - 1$ の番号が付けられています。あなたが $0$ 以上 $N - 1$ 以下の非負整数からなる列 $X = (X_1, X_2, \dots, X_{|X|})$ を宣言すると、人々は以下の規則に従って行進を行います:

  1. 各 $i = 0, 1, \dots, N - 1$ について、人 $i$ は広場 $i$ に移動する。
  2. 各 $j = 1, 2, \dots, |X|$ について、この順に以下を行う:
    • 現在広場 $X_j$ にいないすべての人は、広場 $X_j$ の方向へちょうど一つ分の広場だけ移動する。

$0$ 以上 $N - 1$ 以下の整数からなる長さ $M$ の列 $A = (A_0, A_1, \dots, A_{M-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$ について、$i$ 番目のクエリに対する答え $\text{ans}_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.