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$ คำถาม สำหรับแต่ละ $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.