Median of the subarray.

Правка en1, от v0rtex, 2021-10-11 23:22:38

If you are given an unsorted array of size N and some queries Q which consists of l,r as the range of the subarray. The task is to find the median of this subarray. 1<=N,Q<=5*10^4. Now if we sort the subarray per query the time complexity will be Q*nlogn (here n is the length of the subarray) which will give us TLE. Can anybody share the optimal approach?

Теги range query, median, sorting, time limit exceeded

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский v0rtex 2021-10-11 23:22:38 381 Initial revision (published)