Trung vị
Đề bài
Mô tả
Cho mảng gồm số nguyên . Có truy vấn, mỗi truy vấn gồm hai số nguyên và (), bạn cần tìm trung vị của đoạn con .
Trung vị của một dãy gồm số nguyên là giá trị đứng ở vị trí (đánh số từ ) sau khi sắp xếp dãy tăng dần.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và (, ) là độ dài mảng và số truy vấn.
Dòng thứ hai chứa số nguyên ().
Mỗi dòng trong dòng tiếp theo chứa hai số nguyên và () mô tả một truy vấn.
Dữ liệu ra
Với mỗi truy vấn, in ra trung vị của đoạn con tương ứng trên một dòng.
Ràng buộc
- .
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 8 5 2 8 4 16 5 2 10 6 1 3 2 5 6 8 5 8 1 8 |
4 5 6 5 5 |
Đoạn là , sau khi sắp xếp là ; vị trí là . |
| 3 3 3 1 2 1 3 1 2 3 3 |
2 1 2 |
Với độ dài chẵn, trung vị là phần tử nhỏ hơn trong hai phần tử giữa. |
Bình luận