Trộm Nhà Không Kề

Buổi 27 — Segment Tree cơ bản
Points
36
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Một tên trộm đi dọc dãy N ngôi nhà, nhà i có a_i đồng (có thể âm vì là nhà có bẫy). Hắn không được đột nhập hai nhà kề nhau. Với mỗi dãy nhà [l, r], tìm tổng lớn nhất hắn có thể thu được (có thể không đột nhập nhà nào). Giá trị các nhà có thể thay đổi.

Dữ liệu vào

Dòng đầu chứa hai số nguyên N và Q. Dòng thứ hai chứa N số nguyên a_1..a_N. Q dòng tiếp theo, mỗi dòng là một trong hai dạng:

  • 1 i x: gán a_i = x.
  • 2 l r: truy vấn trên đoạn [l, r].
Dữ liệu ra

Với mỗi truy vấn loại 2, in ra tổng lớn nhất của một tập các chỉ số trong [l, r] không có hai chỉ số kề nhau (tập rỗng cho tổng 0).

Ví dụ
Input Output
5 4\n-546566161 -654964683 -655964757 -697337722 -321325943\n1 4 -525016087\n2 2 4\n2 1 5\n1 2 -979757299 0\n0
Giới hạn
  • 1 ≤ N, Q ≤ 10^5
  • |a_i|, |x| ≤ 10^9
Draft saved