Approach-
A segment tree where each node stores a sorted sub-interval of elements. Building Time- O(n log(n))
Querying and Binary Search- Takes *O(log(n)log(n))
Total TC- O(nlog(n)+log^2(n))
I know this can be solved by persistent segment tree and BIT as well,but i have read on forums that this solution is accepted as well. But its giving TLE…can anyone help??
I don’t think O(nlog(n) + mlog(n)*log(n)) will work with Java. Try doing it with a Persistent Segment Tree or do it in c++.
I haven’t learnt persistent segment tree yet… will have to do it now…SPOJ is really troublesome for java users 