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$. عندما تعلن عن متتالية $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$ استعلامات فورية (online). لكل $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.