Kỷ Lục Mọi Thời Đại
Points
75
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề bài
Một dãy N cổ phiếu có giá hiện tại a_i. Giá của một dãy cổ phiếu liên tiếp có thể tăng hoặc giảm một lượng x. Với mỗi câu hỏi [l, r], hãy cho biết mức giá cao nhất mà bất kỳ cổ phiếu nào trong [l, r] từng đạt được tại BẤT KỲ thời điểm nào trong quá khứ (kể cả giá ban đầu và thời điểm hiện tạ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 giá trị lớn nhất mà một a_i (i ∈ [l, r]) từng có tại một thời điểm bất kỳ trước hoặc ngay lúc này.
Dữ liệu ra
Với mỗi thao tác loại 2, in ra kỷ lục tìm được.
Ví dụ
| Input | Output |
|---|---|
| 5 4\n4 -2 6 3 -2\n2 3 3\n2 1 2\n1 1 1 4\n1 3 4 -7 | 6\n4 |
Giới hạn
- 1 ≤ N, Q ≤ 10^5
- |a_i|, |x| ≤ 10^9
Community Discussion