Đỉnh tải trên từng khoảng

Bối cảnh và bài toán

Một cụm máy chủ lưu mức tải tại n thời điểm. Hệ thống cho phép cập nhật một thời điểm và truy vấn mức tải lớn nhất trên một khoảng liên tiếp.

Yêu cầu

Hỗ trợ lệnh cập nhật và truy vấn cực đại đoạn.

Input

• Dòng 1 chứa n q.
• Dòng 2 chứa n giá trị ban đầu.
• SET i x: gán a[i]=x.
• MAX l r: in giá trị lớn nhất trong [l,r].

Output

In đáp án cho mỗi lệnh MAX.

Ràng buộc

• 1 <= n, q <= 2 * 10^5
• -10^9 <= a[i], x <= 10^9
• 1 <= i <= n
• 1 <= l <= r <= n

Chấm điểm

Ví dụ 1

Input

5 5
1 9 3 7 2
MAX 1 5
SET 2 0
MAX 1 3
SET 5 11
MAX 4 5

Output

9
3
11

Giải thích. Các cực đại thay đổi sau cập nhật điểm.

Ví dụ 2

Input

3 3
-5 -2 -9
MAX 1 3
SET 2 -10
MAX 1 2

Output

-2
-5

Giải thích. Identity của truy vấn cực đại phải xử lý đúng số âm.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.