Cộng Dồn Và Hạ Trần
Points
95
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề bài
Một dãy N cảm biến, cảm biến i đang đo a_i. Hệ thống có hai loại lệnh trên một đoạn: cộng thêm x vào mọi giá trị (x có thể âm), và 'hạ trần': mọi giá trị lớn hơn x bị đặt lại đúng bằng x. Hãy trả lời tổng và giá trị lớn nhất của các đoạn được hỏi. Gợi ý: Segment Tree Beats với hai tag cộng (cho phần tử lớn nhất và cho các phần tử còn lạ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 x: với mọi i ∈ [l, r]: a_i = min(a_i, x).3 l r: hỏi a_l + ... + a_r.4 l r: hỏi max(a_l..a_r).
Dữ liệu ra
Với mỗi thao tác loại 3 hoặc 4, in ra kết quả tương ứng.
Ví dụ
| Input | Output |
|---|---|
| 5 4\n-1 -4 7 2 -9\n4 3 4\n4 5 5\n1 3 4 -6\n2 1 1 -1 | 7\n-9 |
Giới hạn
- 1 ≤ N, Q ≤ 10^5
- |a_i| ≤ 10^9; |x| ≤ 10^4 cho thao tác loại 1; |x| ≤ 10^9 cho thao tác loại 2
Community Discussion