Universal Cup Judging System

Universal Cup

Süre Sınırı: 3.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

有一個公園,裡面有 $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.