olp_066
Xem dạng PDFOLP_066 Truy vấn đoạn con liên tiếp lớn nhất có cập nhật
Truy vấn đoạn con liên tiếp lớn nhất có cập nhật Cho một dãy số nguyên gồm n phần tử a1, a2, ..., an ( 1 ...<= n ...<= 10^5 , ai ...<= 10^9 ) và q truy vấn ( 1 ...<= q ...<= 10^5 ).
Có hai loại truy vấn: 1 pos val: Gán giá trị phần tử tại vị trí pos thành val ( 1 <= pos<= n , val <= 10^9 ). 2 l r: Tìm tổng lớn nhất của một đoạn con liên tiếp (không rỗng) nằm hoàn toàn trong đoạn [l, r] ( 1 ...<= l ...<= r ...<= n ). Tức là tìm giá trị lớn nhất của các giá trị a_k từ u đến v với l<=u<=v<=r
Input
Dòng đầu chứa hai số nguyên n và q .
Dòng thứ hai chứa n số nguyên a1, a2, ..., a_n .
q dòng tiếp theo, mỗi dòng mô tả một truy vấn theo định dạng 1 pos val hoặc 2 l r.
Output Với mỗi truy vấn loại 2 l r, in ra một số nguyên duy nhất là tổng đoạn con liên tiếp lớn nhất tìm được trên đoạn [l, r] . Ví dụ Input
5 4
3 -5 4 2 -1
2 1 5
1 2 6
2 1 5
2 3 4
Output
6
15
6
Bình luận