Let's build merge-sort tree on our array. We can use binary search to check if the given value k is less than or equal to the median of subarray. Let's decompose interval into segments on our merge-sort tree. We can sum up the number of elements that are less than or equal to k in each of the segments with lower_bound or sth. similar. Based on this sum we can make transitions in binary search (if the sum is smaller than (r-l+1)/2 then the median is bigger etc). We can answer each query in O(log^3 N) since we use lower_bound on O(log N) segments in each iteration of binary search. I hope my explanation is clear.

This problem can easily be reduced to SPOJ's MKTHNUM task. There are a variety of solutions to that including a $$$\mathcal{O}(QlogN)$$$ one using persistent segment tree.

Mo's algorithm should also work here as $$$N, Q$$$ is not that big. Using a built-in order statistic tree or Segment Tree to quickly find median give us an $$$O((N + Q) * \sqrt{N} * log(N))$$$ solution!

There 3(maybe more) methods of solving this problem.

1) Persistent Segment Tree

Finding the k-th smallest number in a range

In this task you just need find $$$n/2$$$-th smallest number in a range.

Complexity : $$$O($$$ $$$N$$$$$$log(N)$$$ $$$+$$$ $$$Q$$$ $$$*$$$ $$$log$$$$$$(N)$$$$$$)$$$

2) Merge Sort Tree.

Saving the entire subarrays in each vertex:

(Described in the other comment)

Complexity : $$$O($$$ $$$N$$$$$$log(N)$$$ $$$+$$$ $$$Q$$$ $$$*$$$ $$$log^3$$$$$$(N)$$$$$$)$$$

3) Mo's algorithm

Mo's algorithm

If you want to solve it with MO's algorithm you need to use some data structure that can :

• Add element

• Delete element

• Find the $$$n/2$$$-th element of the multiset.

You can use segment tree to do this.

Complexity : $$$O($$$ $$$Q$$$$$$log(Q)$$$ $$$+$$$ $$$(N + Q)$$$ $$$*$$$ $$$log$$$$$$(N)$$$ $$$*$$$ $$$sqrt(N)$$$ $$$)$$$

Sorry for my bad english.

Ok I think we can solve it by maintaining one min and one max heap. Like we do in case of finding median of stream of numbers. Of course in this case we should do it offline by sorting the queries. As we proceed in the queries in sorted order we will encounter some addition or deletion so just keep balance between these two heap. Time complexity would be $$$O(NlogN+QlogQ)$$$.

I think it should work but you are welcome to point it out if you think it doesn't.

You can solve this using a Trie in $$$O((N + Q) \log N \log max(A_i))$$$, build a Trie and insert each number from left to right as a padded decimal string, and while inserting, for each Trie Node in path, append the index of the number in node. ie. If values with indices 4, 6, 9 passed through some node while inserting, then node will consist of $$$[4, 6, 9]$$$, if you insert in left to right order, these will be sorted for each node by default.

This allows us to simulate a trie that only consists of elements in a range, for example, if range query is $$$[L, R]$$$ then for each node binary search the count of indices in range $$$[L, R]$$$, this will be number of values with given prefix in given range, Now we can do all query operations on this trie like any usual trie.

For this problem the operation is $$$Kth$$$ smallest element in Trie $$$(K = N / 2)$$$.

This can be performed as shown in this blog https://codeforces.net/blog/entry/104650

All we do is replace node frequency with binary search on indices in range, This solves the problem, and we can also extend this idea to allow updates (delete old and insert new) by keeping ordered set in each Trie Node, which allows $$$O(\log N \log max(A_i))$$$ updation but higher constant factor.