MEDIAN QUERY
Xem PDF
Điểm:
200 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho một dãy số nguyên dương \(a_1,a_2,...,a_n\) gồm \(n\) phần tử. Bạn sẽ phải trả lời \(q\) truy vấn, mỗi truy vấn trả lời số trung vị của đoạn \([A_L;A_R]\) \((1 \le L \le R \le n)\).
Định nghĩa: Số trung vị của 1 dãy số là số nằm ở vị trí thứ \(\frac{n}{2} + 1\) sau khi sắp xếp dãy đó tăng dần (với \(n\) lẻ) hoặc ở vị trí thứ \(\frac{n}{2}\) (nếu \(n\) chẵn).
Input
- Dòng đầu chứa số nguyên dương \(n\) không quá \(10^5\).
- Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,a_2,...,a_n\) \((a_i \le 10^5)\)
- Dòng thứ ba chứa số nguyên dương \(q\) không quá \(1000\) - số truy vấn cần trả lời.
- \(q\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương \(L, R\) \((1 \le L \le R \le n)\)
Output
- Ứng với mỗi truy vấn, in ra kết quả thỏa mãn đề bài.
Example
Test 1
Input
6
7 9 1 7 8 2
3
1 3
3 6
1 1Output
7
2
7
Bình luận
;-; xin lỗi nãy tôi bình luận vô tri
ai giải thích hộ em cái ví dụ với ạ em chưa hiểu lắm :((
adu WYSI
Gửi tới admin: Em không biết là ai đã đổi nhưng nếu có thay đổi gì thì nhờ các thầy/cô/anh/chị ghi chú vào giúp em để em biết ạ, em cảm ơn. (Cụ thể là ai đó đã đổi dạng bài từ
a_luyen tap (thầy Đông)sangBài toán truy vấn (Query))brute-force go brrrrrrrrrrrrrrrrrr
bài ni cày trâu vẫn ăn mà nhỉ????
hao tu segment tree???
dùng cây index vẫn bị rte :