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. Trước cập nhật, các tổng tiền tố của đoạn [1,4] là -5, 5, 2, 6, vì vậy kết quả đúng là 6 (chọn toàn bộ 4 phần tử). Sau khi gán phần tử thứ 2 bằng -1, mọi tiền tố của [1,4] đều âm nên kết quả là 0; trên [3,4], tổng tiền tố tốt nhất là 1.

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.