Đê chắn lũ
Đề bài
Mô tả
Dọc theo một con sông có đoạn đê liên tiếp, đoạn thứ có chiều cao ban đầu là . Một đoạn đê được gọi là an toàn nếu chiều cao của nó không nhỏ hơn ngưỡng . Trong mùa mưa, trung tâm điều hành phải xử lý yêu cầu thuộc một trong bốn loại sau:
- Loại 1: cho ba số , yêu cầu hạ toàn bộ các đoạn đê trong đoạn xuống không vượt quá , tức gán với mọi .
- Loại 2: cho hai số , yêu cầu tính tổng chiều cao của các đoạn đê từ đến .
- Loại 3: cho hai số , yêu cầu tìm chiều cao lớn nhất của một đoạn đê trong đoạn .
- Loại 4: cho hai số , yêu cầu đếm số cụm an toàn trong đoạn . Một cụm an toàn là một đoạn con liên tiếp cực đại (trong ) chỉ gồm các đoạn đê an toàn.
Yêu cầu: Hãy trả lời mọi truy vấn loại 2, loại 3 và loại 4.
Dữ liệu vào
- Dòng đầu chứa ba số nguyên .
- Dòng tiếp theo chứa số nguyên dương .
- dòng tiếp theo mô tả các truy vấn. Với truy vấn loại 1, ta có . Với truy vấn loại 2, 3 hoặc 4, ta có với và .
Dữ liệu ra
Với mỗi truy vấn loại 2, loại 3 và loại 4, ghi ra trên một dòng kết quả tương ứng.
Ràng buộc
- ,
- ,
Subtasks
- Subtask 1 ( số điểm): .
- Subtask 2 ( số điểm): không có truy vấn loại 1.
- Subtask 3 ( số điểm): mọi truy vấn loại 1 đều có và .
- Subtask 4 ( số điểm): .
- Subtask 5 ( số điểm): không có ràng buộc gì thêm.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 8 5 7 2 6 5 9 3 4 1 6 1 2 5 6 2 1 6 1 1 4 4 4 1 6 3 1 6 1 5 5 1 4 1 6 |
2 29 1 6 0 |
Ban đầu các đoạn an toàn là , nên trong đoạn có hai cụm an toàn: và . Sau khi hạ đoạn xuống không vượt quá , dãy trở thành nên tổng là . Hạ đoạn xuống không vượt quá , chỉ còn vị trí an toàn: có cụm, chiều cao lớn nhất là . Cuối cùng hạ vị trí xuống thì không còn cụm an toàn nào. |
| 5 7 3 3 4 1 3 5 4 2 5 1 1 5 3 2 1 5 4 1 5 1 4 4 2 4 1 5 3 2 4 |
2 13 2 2 3 |
Ví dụ thêm (không có trong đề gốc). Đoạn đê có chiều cao đúng bằng vẫn an toàn. Trong có hai cụm và . Sau khi hạ cả dãy xuống không vượt quá , dãy là với tổng và hai cụm. Hạ vị trí xuống : còn hai cụm và ; chiều cao lớn nhất trong là . |
Bình luận