Đoạn Lãi Lớn Nhất

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

Một nhà đầu tư theo dõi lãi/lỗ của N ngày liên tiếp (a_i có thể âm). Với mỗi lần hỏi [l, r], anh ta muốn chọn một đoạn ngày liên tiếp không rỗng nằm trong [l, r] sao cho tổng lãi lớn nhất. Dữ liệu có thể được cập nhật.

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 đoạn con liên tiếp không rỗng của a_l..a_r.

Ví dụ
Input Output
5 4\n-128086863 -443226333 -378513597 -724858855 -86521562\n1 1 -794090188\n2 2 2\n2 1 3\n2 1 2 -443226333\n-378513597\n-443226333
Giới hạn
  • 1 ≤ N, Q ≤ 10^5
  • |a_i|, |x| ≤ 10^9
Draft saved