[ ลืมรหัสผ่าน | ลงทะเบียนสมาชิกใหม่ ]    
  


1072 : บัญชาแห่งจำนวน (number)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 8 megabyte(s)
สถิติโจทย์ข้อนี้ : ใช้เวลาน้อยที่สุด ทั้งหมด

    คุณ และนักโบราณคดีหลบระเบิดมาได้อย่างเฉียดฉิว ทำให้เทพเจ้าแห่งตัวเลขตกใจเป็นอย่างมาก อย่างไรก็ดีก่อนที่เทพเจ้าจะยอมรับว่าคุณและนักโบราณคดีไม่ใช่ผู้ตั้งใจลบ หลู่ เป็นเพียงแค่หมู่คนที่จริงๆ แล้วมีสัมมาคารวะ เพียงแต่ยังไม่รู้กาลเทศะดีเท่านั้น เทพเจ้าต้องการทดสอบคุณเป็นขั้นสุดท้าย

    เทพเจ้ากำหนดให้มีลำดับจำนวนเต็ม N จำนวน แทนด้วย a1,a2,a3,...,aN โดยที่ 0 ≤ ai ≤ 109 และกำหนดให้มีปฏิบัติการกับลำดับของตัวเลขนี้ 4 ประเภทดังนี้

  • การเวียนวนตัวเลข (a) เมื่อกำหนดค่าจำนวนเต็มบวก x และ y มาให้ หน้าที่ของคุณคือการสลับค่าของ ax และ ay (ค่า x และ y อาจเท่ากันได้)
  • การจำแลงตัวเลข (b) เมื่อกำหนดจำนวนเต็มบวก x และ k หน้าที่ของคุณคือแทนค่า ax ใหม่ด้วยค่า k ที่รับเข้ามา
  • การปัดเป่าตัวเลข (c) เมื่อกำหนดจำนวนเต็มบวก x หน้าที่ของคุณคือแบ่งตัวเลขออกเป็นส่องกลุ่ม กลุ่มแรกคือตัวเลข x ตัวแรก และกลุ่มที่สองคือตัวเลข N - x ตัวที่เหลือ หลังจากนั้นให้เรียงตัวเลขทั้งสองกลุ่มจากหลังไปหน้าแล้วนำมาต่อกัน กล่าวคือ เปลี่ยนลำดับจาก  a1,a2,a3,...,aN  ให้เป็น ax,ax-1,ax-2,...,a2,a1,an,an-1,an-2,...,ax+2,ax+1
  • การออกดอกของตัวเลข (q) เมื่อกำหนดจำนวนเต็ม x หน้าที่ของคุณบอกเทพเจ้าว่า ax มีค่าเท่าใด
งานของคุณ
    จงเขียนโปรแกรมรับลำดับตั้งต้นและรายการปฏิบัติการที่เทพเจ้าสั่งตามลำดับก่อนหลัง แล้วแสดงผลลัพธ์ตัวเลขของปฏิบัติการออกดอกของตัวเลข ออกมาตามลำดับในข้อมูลเข้า

ข้อมูลนำเข้า
    บรรทัดแรกมีจำนวนเต็ม N และ M (1 ≤ N, M ≤ 500,000) แสดงความยาวของลำดับตัวเลข และจำนวนปฏิบัติการตามลำดับ
    อีก N บรรทัดถัดมา มีข้อมูลของจำนวนเริ่มต้นในลำดับ  โดยในบรรทัดที่ i + 1 ของข้อมูลนำเข้าจะมีจำนวนเต็มหนึ่งตัว แทนค่า ai
    อีก M บรรทัดถัดมา มีข้อมูลของปฏิบัติการที่เทพเจ้าสั่งให้คุณทำ โดยแต่ละบรรทัดจะมีรูปแบบหนึ่งในสี่แบบดังต่อไปนี้
  • “a x y”  โดย x, y คือจำนวนเต็มซึ่ง 1 ≤ x, y ≤ N หมายความว่าให้ทำการเวียนวนตัวเลขด้วยค่า x และ y ที่กำหนด
  • “b x k”  โดย x เป็นจำนวนเต็มซึ่ง 1 ≤ x ≤ N และ k เป็นจำนวนเต็มซึ่ง 0 ≤ k ≤ 109 หมายความว่าให้ทำการจำแลงตัวเลขด้วยค่า  และ  ที่กำหนด
  • “c x”  โดย x เป็นจำนวนเต็มซึ่ง 1 ≤ x ≤ N หมายความว่าใหทำการปัดเป่าตัวเลขด้วยค่า  ที่กำหนด
  • “q x” โดย x เป็นจำนวนเต็มซึ่ง 1 ≤ x ≤ N หมายความว่าให้ทำการออกดอกตัวเลขโดยใช้ค่า  ที่กำหนด
ข้อมูลส่งออก
    มี D บรรทัดเมื่อ D คือจำนวนการออกดอกตัวเลขในข้อมูลเข้า โดยในบรรทัดที่ i ให้พิมพ์คำตอบของการออกดอกตัวเลขครั้งที่ i ตามลำดับก่อนหลังในข้อมูลเข้า

อธิบายตัวอย่างข้อมูลนำเข้า

ข้อมูลนำเข้า ข้อมูลส่งออก คำอธิบาย
5 6   รับค่า N = 5,M = 6
1   กำหนดค่า a1  = 1
3   กำหนดค่า a2  = 3
4   กำหนดค่า a3  = 4
5   กำหนดค่า a4  = 5
2   กำหนดค่า a5  = 2
q 3 4 แสดงค่า a3
b 3 6   ลำดับของจำนวนใหม่คือ 1 3 6 5 2
a 2 4   ลำดับของจำนวนใหม่คือ 1 5 6 3 2
q 2 5 แสดงค่า a2
c 1   ลำดับของจำนวนใหม่คือ 1 2 3 6 5
q 4 6 แสดงค่า a4

การให้คะแนน
        50% ของชุดข้อมูลทดสอบ มีค่า N ≤ 5,000 และ M ≤ 5,000 และในทุกชุดข้อมูลทดสอบมีค่า N ≤ 500,000 และ M ≤ 500,000

ที่มา: การแข่งขัน YTOPC Challenge เมษายน 2552

ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
5 6
1
3
4
5
2
q 3
b 3 6
a 2 4
q 2
c 1
q 4 		4
5
6

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้