Hi I have been trying to solve this problem http://www.spoj.com/problems/KL11B/ The solution I have found so far uses BIT + Treap(Balanced Tree) and worst case complexity is log^2(n) for each query. Some users have accepted the problem using a lot less time and memory than other users that I know they used this solution. Is there a faster solution to this problem or it was just constant optimization?, would there be a faster to code solution to this problem having at most log^2(n) complexity for each query.
oops. It was wrong soory, I didn't get statement clearly.
ADD: Using BIT + Treap got AC code
Really nice implementation, but your time is three times greater than best solution. I wonder what they implemented to get that time..
My best was 15.2 secs, you can implement treap non-recursively, it should be much more faster.