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, -10⁹ <= Z <= 10⁹)
• 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

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