Tổng tập độc lập lớn nhất với cập nhật điểm
Points
45
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 hai loại:
1 p v: Gán $A_p = v$.2 l r: Chọn một tập con các chỉ số (có thể rỗng, khi đó tổng bằng $0$) trong đoạn $[l, r]$ sao cho không có hai chỉ số liên tiếp nào cùng được chọn và tổng giá trị là lớn nhất.
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 tổng lớn nhất trên một dòng.
Ví dụ
Input
5 3
3 2 7 10 1
2 1 5
1 4 1
2 1 5
Output
13
11
Giới hạn
$1 \le n, q \le 10^5$, $|A_i|, |v| \le 10^9$.
Community Discussion