trang chủ / đề bài / icpc22_mt_d

Trung vị

Đề bài

Mô tả

Cho mảng a gồm n số nguyên a1,a2,…,an. Có q truy vấn, mỗi truy vấn gồm hai số nguyên l và r (l≤r), bạn cần tìm trung vị của đoạn con al,al+1,…,ar.

Trung vị của một dãy gồm m số nguyên là giá trị đứng ở vị trí ⌊(m+1)/2⌋ (đánh số từ 1) 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 n và q (1≤n≤105, 1≤q≤105) là độ dài mảng và số truy vấn.

Dòng thứ hai chứa n số nguyên a1,a2,…,an (1≤ai≤105).

Mỗi dòng trong q dòng tiếp theo chứa hai số nguyên l và r (1≤l≤r≤n) 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

  • 1≤n,q≤105.
  • 1≤ai≤105.
  • 1≤l≤r≤n.

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 [2,5] là 8,4,16,5, sau khi sắp xếp là 4,5,8,16; vị trí ⌊5/2⌋=2 là 5.
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

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0