Chuỗi Lãi Sau Điều Chỉnh

Buổi 28 — Segment Tree Lazy
Points
34
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Công ty ghi lãi/lỗ của N tháng liên tiếp. Do điều chỉnh kế toán, toàn bộ các tháng trong một đoạn có thể được đặt lại cùng một giá trị x. Với mỗi câu hỏi [l, r], tìm tổng lớn nhất của một dãy tháng liên tiếp không rỗng nằm trong [l, r].

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 thao tác:

  • 1 l r x: gán a_i = x với mọi i ∈ [l, r].
  • 2 l r: hỏi 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.
Dữ liệu ra

Với mỗi thao tác loại 2, in ra kết quả.

Ví dụ
Input Output
5 4\n6 -2 3 1 6\n1 5 5 0\n2 5 5\n1 5 5 -5\n1 3 4 -1 0
Giới hạn
  • 1 ≤ N, Q ≤ 10^5
  • |a_i|, |x| ≤ 10^9
Draft saved