Universal Cup Judging System

Universal Cup

Time Limit: 3.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

有一個公園,入面有 $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$ 嘅方向移動啱啱好一個廣場。

畀定一個長度為 $M$ 嘅序列 $A = (A_0, A_1, \dots, A_{M-1})$,由介乎 $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.