Prefix sum queries
Xem PDF
Điểm:
1600 (p)
Thời gian:
1.0s
Bộ nhớ:
508M
Input:
bàn phím
Output:
màn hình
Cho dãy gồm \(n\) số nguyên, bạn cần phải thực hiện \(q\) truy vấn thuộc các loại sau:
- Cập nhật giá trị của phần tử thứ \(k\) thành \(u\)
- Trả lời câu hỏi: Trong mọi đoạn con bắt đầu từ \(a\), kết thúc tại \(i (a \le i \le b)\) thì đoạn con có tổng lớn nhất là bao nhiêu?
Input
- Dòng đầu tiên chứa hai số nguyên \(n,q\): độ dài dãy và số truy vấn
- Dòng thứ hai chứa \(n\) số nguyên \(x_1, x_2, ..., x_n\): giá trị lúc đầu của dãy
Cuối cùng là \(q\) dòng mô tả các truy vấn. Mỗi dòng chứa ba số nguyên 1 k u hoặc 2 a b
Output
- In ra đáp án của mỗi truy vấn loại \(2\)
Constraints
Trong tất cả các test
- \(1\le n,q\le 2⋅10^5\)
- \(−10^9\le x_i,u\le 10^9\)
- \(1\le k\le n\)
- \(1\le a\le b\le n\)
Example
Test 1
Input
8 4
1 2 -1 3 1 -5 1 4
2 2 6
1 4 -2
2 2 6
2 3 4Output
5
2
0
Bình luận
Ủa sao cái output cuối cùng lại là 0 nhỉ, đáng lẽ phải là -1 chứ :V