Tổng đoạn con lớn nhất với cập nhật
Points
60
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho dãy gồm $N$ số nguyên $A_1, A_2, \dots, A_N$ và $Q$ truy vấn thuộc một trong hai loại sau:
1 idx val: Gán $A_{idx} = val$.2 l r: Tìm tổng lớn nhất của một đoạn con liên tiếp khác rỗng nằm hoàn toàn trong $[l, r]$.
Dữ liệu vào
- Dòng đầu tiên 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 đoạn con lớn nhất tìm được trên một dòng.
Ví dụ
| Input | Output |
|---|---|
| 5 3 -2 1 -3 4 -1 2 1 5 1 3 5 2 1 5 |
4 10 |
Giới hạn
$1 \le N, Q \le 10^5$, $|A_i|, |val| \le 10^9$.
Community Discussion