Cập nhật điểm và tổng đoạn con lớn nhất

Buổi 03 — Mảng 1 Chiều
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Submissions
Đề 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$.

Draft saved