Gửi bài giải

Điểm: 10,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 501M
Input: stdin
Output: stdout

Dạng bài

OLP_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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.