LushoPlusPlus So the idea is to replace each element of the given array by it's compressed value [index of this element if we sort the whole array]. It's simply done in $$$O(n.log(n))$$$. Also, save the inverse mapping, i.e. $$$pos[compressed$$$ $$$value(a[i])] = i$$$.

Now, we will use this array $$$pos[1..n]$$$ to answer queries $$$l,r,k$$$. How ? the first index $$$i$$$ such that $$$l \le pos[i] \le r$$$ will be the smallest compressed value in $$$a[l..r]$$$. Next index satisfying the inequality will be second smallest value and so on. We have to find the $$$k_{th}$$$ such index.

Build partial frequencies of each element [and for each block]. Break $$$a[1..n]$$$ into $$$\sqrt n$$$ blocks. Iterate through blocks and in each, find number of elements satisfying the inequality use partial frequencies. The first block where number of elements $$$\ge k$$$, traverse it using brute force.

• Build merge sort tree
• During traversal on merge sort tree, divide current interval from middle then if ask is there enough number at left one in O(logN) , if enough go left else right.
• Maximum depth of traversal is O(log N) and each depth has O(log N) complexity.
• Overall complexity is O(log^2 N) at each query.

I use persistent segment tree to create n trees in O(nlogn) time. That means, that I do not modify any tree node. Instead I create a new node every time. This way I can always use any old version of a tree. Each update operation on a segment tree takes O(logN) time, O(logN) additional memory and produces a root of new segment tree, that reuses some parts of an old one. Anytime a node would be modified in a simple segment tree a new node with another value should be created in a persistent one. A tree for [1...k] is just tree for [1..k-1] where some element with a value x is replaced to some element with value (x + 1).

I slightly modified the code for it to fit to SPOJ version of a problem, though I didn't change the point. This version gets AC on SPOJ.

About functions:

allocate(x = 1) allocates exactly x segment tree nodes from a constant array. A pointer to the first of them is returned

update(v, vl, vr, x) increases by one the value of x node in subtree tree rooted in v, where [vl; vr-1] is segment corresponding to that subtree. In all outer functions it is used that way: update(v, 0, maxn, x). That functions returns the root of a new subtree leaving the original untouched.

find_nth(u, v, vl, vr, nth) finds an nth element on a tree that is difference of v and u. vl and vr are the boundaries of a subsegment this function is operating on now. It returns a pair of a current result and a flag — should we continue searchin to the right, or not. That flag is not used outside of that function

array — input array

coords — sorted input array. It is used to replace numbers in range [-10^9; 10^9] with numbers in range [0...n-1]

Yes, it's O(M log^2 N)... I sort the array, and then create N segment trees (only the first one is allocated entirely, the other ones only allocate the differences (log(N) nodes)), that store how many elements in a certain range appear in that tree. The first tree will have 1 element in total, the second one will have 2, ..., the last one will have a total of N elements.

After that, I search the trees using binary search until I find the first tree that has K nodes in the range L..R.

How can I make it O(M log N) ????

Good. I recoded it and now the solution is O((M+N) log N).

Here is the updated solution -> Code