Perfect, and brilliant! I tried to prove it but didn't succeed :p This now explains why its a fast solution (and BTW tourist did it too 85990887, not sure if he proved it in his mind :D ).

Interestingly, I think this kind of resonates with my memory that in general $$$\sqrt n$$$-decomposition related problems can be solved by binary division algorithms too, like the classic range add-update-query problem which can be solved via both sqrt or segment trees. Not sure if there is a deeper reason behind that :)

No I meant time is q*n*logn. Sorry the last sentence of my last reply is wrong. That's for space not related to time. But runtime wise, your qLog^2n is even smaller than the output size n*sqrt(q), e.g. if q=1E4 and n=1E6. That couldn't happen, right?

The solution is inspiring! But the complexity isn't as low as O(q * log^2 n). In worst case, there could be O(min(n^2, q*n)) index sub-ranges over the course, each costing O(log^2 n) look-ups down the tree.

Thus I think time should be O(min(n^2 * log^2 n, q*n * log^2 n)). It's just that getting into that worse case is really hard either by random or manual input, so the answer is low enough to pass the 2.2*10^6 limit.

Just say, fuck windows.

Time flies! Codeforces #100 is my first round, and now it comes to #200 rapidly.
It gives a lot of fun, hope it to be better and better.
(of course it's already terrific now, except the network speed some times... )

Is that you are elder because your name is "eldar" :P (just joke)

Excuse me, would you like to give me the photo of team 007 (us)? Thanks!

Any info. about the score calculating rules? As usual?