Hạ Trần Giới Hạn
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề bài
Một dãy N máy phát điện, máy i đang phát a_i đơn vị công suất. Khi có lệnh giới hạn, mọi máy trong một đoạn có công suất vượt quá x sẽ bị hạ xuống đúng bằng x (máy có công suất ≤ x giữ nguyên). Hãy trả lời công suất lớn nhất và tổng công suất trong các đ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: với mọi i ∈ [l, r]: a_i = min(a_i, x).2 l r: hỏi max(a_l..a_r).3 l r: hỏi a_l + ... + a_r.
Dữ liệu ra
Với mỗi thao tác loại 2 hoặc 3, in ra kết quả tương ứng.
Ví dụ
| Input | Output |
|---|---|
| 5 4\n1 8 1 5 1\n3 5 5\n1 5 5 5\n2 4 4\n2 1 5 | 1\n5\n8 |
Giới hạn
- 1 ≤ N, Q ≤ 10^5
- 1 ≤ a_i, x ≤ 10^9
Community Discussion