1147 : Segment Tree
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
คุณเป็นคน ๆ หนึ่งที่ต้องการฝึกเขียน Segment Tree คุณจึงมาทำโจทย์ข้อนี้
กำหนดอาเรย์ N ช่อง (ทุกช่องมีค่าเริ่มต้นเป็น 0) และกำหนดคำสั่ง Q คำสั่งซึ่งมีทั้งสิ้น 2 ชนิด ดังนี้
  1. เปลี่ยนค่าอาเรย์ช่องที่ i ให้มีค่าเท่ากับ Z
  2. หาค่า max ของตัวเลขทุกตัวระหว่างช่อง A ถึง B
ข้อมูลนำเข้า
บรรทัดแรกจำนวนเต็ม N และ Q แทนจำนวนช่องของอาเรย์และจำนวนคำสั่ง (1 <= N, Q <= 262,144)
ต่อมา Q บรรทัดจะประกอบด้วยคำสั่ง 2 ลักษณะ ดังนี้
  • U i Z :  เปลี่ยนค่าอาเรย์ช่องที่ i ให้มีค่าเท่ากับ Z (1 <= i <= N, -109 <= Z <= 109)
  • P A B : แสดงผลค่าที่มากที่สุดของเลขในอาเรย์ช่องที่ A, A+1, A+2, … , B (1 <= A <= B <= N)
ข้อมูลส่งออก
ประกอบด้วย K บรรทัด เมื่อ K คือจำนวนของคำสั่ง “P” บรรทัดละ 1 จำนวน แทนคำตอบของคำถามแต่ละครั้ง

ที่มา: Programming.in.th ( PS.int )
ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
5 4
U 1 -14
U 1 -1
P 2 2
P 3 5
0
0
6 7
U 5 280
U 1 7
P 1 2
P 3 5
U 4 -873760809
U 2 -392
P 1 1
7
280
7

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

กำลังออนไลน์: 12 ผู้เยี่ยมชมและ 4 สมาชิก (1 บอท)