Số nhỏ thứ k
Đề bài
Mô tả
Tại thành phố nọ, có cột đá, cột đá thứ có chỉ số kỹ năng . Bạn được giao nhiệm vụ xử lý truy vấn thuộc hai loại sau đây:
- Loại 1: . Đây là truy vấn cập nhật: chỉ số kỹ năng của cột đá thứ được thay đổi thành .
- Loại 2: . Đây là truy vấn báo cáo: yêu cầu tìm giá trị kỹ năng nhỏ thứ trong đoạn các cột đá từ đến (tính cả và ).
Dữ liệu vào
- Dòng đầu tiên gồm một số nguyên dương ;
- Dòng tiếp theo chứa số nguyên dương , chỉ số kỹ năng ban đầu;
- Dòng tiếp theo chứa một số nguyên dương ;
- dòng tiếp theo, mỗi dòng chứa một truy vấn thuộc một trong hai loại:
- ;
- .
Dữ liệu ra
Với mỗi truy vấn Loại 2, in ra kết quả là một số nguyên duy nhất trên một dòng.
Ràng buộc
- .
- .
Subtasks
- Subtask 1 ( số điểm): , .
- Subtask 2 ( số điểm): , và không có truy vấn Loại 1.
- Subtask 3 ( số điểm): , và mọi truy vấn Loại 2 có .
- Subtask 4 ( số điểm): , , .
- Subtask 5 ( số điểm): , và không có ràng buộc bổ sung.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 1 2 3 4 5 3 2 2 4 2 1 3 6 2 2 4 2 |
3 4 |
Đoạn ban đầu là , số nhỏ thứ hai là . Sau khi , đoạn là , số nhỏ thứ hai là . |
| 4 5 5 1 5 3 2 1 4 1 2 1 4 2 2 1 4 4 |
1 5 5 |
Ví dụ thêm (không có trong đề gốc). Sắp xếp đoạn được ; các giá trị bằng nhau được tính riêng. |
| 1 7 3 2 1 1 1 1 1 3 2 1 1 1 |
7 3 |
Ví dụ thêm (không có trong đề gốc). |
Bình luận