Cập nhật điểm và tổng đoạn con lớn nhất
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Đề bài
Cho mảng số nguyên $A$ gồm $n$ phần tử đánh số từ $1$ đến $n$ và $q$ truy vấn thuộc một trong hai loại:
1 p v: Gán $A_p = v$.2 l r: Tìm tổng lớn nhất của một dãy con liên tiếp khác rỗng nằm hoàn toàn trong đoạn $[l, r]$.
Dữ liệu vào
Dòng đầu chứa hai số nguyên $n, q$. Dòng thứ hai chứa $n$ số nguyên $A_1, A_2, \dots, A_n$. $q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn.
Dữ liệu ra
Với mỗi truy vấn loại 2, in ra kết quả trên một dòng.
Ví dụ
Input
5 3
1 -2 3 4 -1
2 1 5
1 2 5
2 1 5
Output
7
13
Giới hạn
$1 \le n, q \le 10^5$, $|A_i|, |v| \le 10^9$.
Community Discussion