Tiền tố tốt nhất trong một đoạn động

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

Một chuỗi số có thể được cập nhật tại từng vị trí. Với truy vấn [a,b], hệ thống không cần tổng toàn đoạn mà cần tổng lớn nhất của một tiền tố bắt đầu từ a và kết thúc tại một vị trí bất kỳ không vượt quá b; tiền tố rỗng với tổng 0 được phép.

Yêu cầu

Hỗ trợ cập nhật điểm và truy vấn tiền tố lớn nhất trong đoạn.

Input

• Dòng 1 chứa n q.
• Dòng 2 chứa n số.
• 1 k u: gán a[k]=u.
• 2 a b: hỏi tổng tiền tố lớn nhất trong [a,b].

Output

In đáp án cho mỗi truy vấn loại 2.

Ràng buộc

• 1 <= n, q <= 2 * 10^5
• -10^9 <= a[i], u <= 10^9
• 1 <= k <= n
• 1 <= a <= b <= n

Chấm điểm

Ví dụ 1

Input

8 4
1 2 -1 3 1 -5 1 4
2 2 6
1 4 -2
2 2 6
2 3 4

Output

5
2
0

Giải thích. Tiền tố rỗng được phép nên đáp án không âm.

Ví dụ 2

Input

4 4
-5 10 -3 4
2 1 4
1 2 -1
2 1 4
2 3 4

Output

6
0
1

Giải thích. Sau cập nhật, đoạn 1..4 không có tiền tố dương nên kết quả là 0.

Thông tin bài tập

• Yêu cầu ngoài OJ: nộp Decision Note theo template đi kèm.

Nguồn: Phỏng theo CSES – Prefix Sum Queries.