Trộm Nhà Không Kề
Points
36
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề 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
Community Discussion