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.