Can anyonre give me a hint how to solve this problem here!

Assuming that you are familiar with segment tree

You can solve this problem by building a segment tree, with a sorted sub-array in every vertex and then divide [l, r] into sub-segments, and do binary search on sub-segments.

You can solve this problem by using Offline solution method and by creating Balance Binary Search Tree incrementallyâ€¦ First iterate over all queries and store for each index what is query on thatâ€¦ While creating Balanced BST you can find out number of smaller elements till now in log(N) using Binary Search tree that we have made till that point, and store answer for that pair(i,k) in some dict ansThatWeFound. Now iterate through query again, for ans(i,j,k) = ansThatWeFound(j,k) - ansThatWeFound(i-1,k). Hope this was clear enough and was providing enough info to approach this question nowâ€¦ I you have some doubt then you can ask that in commentsâ€¦

Using sorted sub-array in every vertex will take n^2 log(n) time, no?? If I am getting correctly what you are sayingâ€¦

\log(n)^2 for each query

noâ€¦ while creating tree itselfâ€¦ Can you post some pseudo code hereâ€¦??

@kauts_kanu, this is also known as mergesort tree. But I had to use input via `getchar_unlocked()`

to get overcome TLE, so be careful about that @phantomhive.

Did not know about thisâ€¦ thanksâ€¦

can i do this with fenwick trees ??

amm creating the tree with sorted subarray will cost me ** N* log(n)* log(logn)**

and for each query it will cost **log(n)*log(log(n))**

An approach for this problem is explained here: http://codeforces.com/blog/entry/10183?#comment-156355.

Can you please share your code with getchar_unlocked() with merge sort tree? I am using it but still getting TLE!

Here is my code - http://ideone.com/gzjsB3

Thanks!!