Đỉnh Núi Dâng Cao

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

Một dãy núi có N đỉnh, đỉnh i cao a_i mét. Các trận động đất làm một dãy đỉnh liên tiếp nhô lên thêm x mét (x có thể âm nếu đất sụt). Hãy cho biết đỉnh cao nhất trong từng đoạn được hỏ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 thao tác:

  • 1 l r x: cộng x vào a_l..a_r.
  • 2 l r: hỏi max(a_l, ..., a_r).
Dữ liệu ra

Với mỗi thao tác loại 2, in ra giá trị lớn nhất trong đoạn.

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