Tổng tập độc lập lớn nhất với cập nhật điểm

Buổi 03 — Mảng 1 Chiều Dynamic Programming
Points
45
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 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$.

Draft saved