i did DQUERY problem in spoj----link http://www.spoj.com/problems/DQUERY/
this is my solution...after referring through some material and blog AND finally got AC....
but ...could any one pls explain what happened between (53-72) lines....i couldnt understand....
pls explain it clearly so tht a beginner of this ALGO could understand.....also pls say if we can write those lines without any confusion if possible..
i would be very thankful to you....
thank you..
First of all, DON'T solve any problem if you don't understand it's concept.
The lines (53-72) they are the main concept of Mo's algorithm, you can see here for more understanding.
Actually, the main concept of Mo's algorithm happens between lines 11 and 15, in the sorting criteria. Lines 53-72 is just adding/removing stuff as we move the two pointers.
It first sorts the queries by block of left end (that is, left position divided by square root of max value (174 seems to be in this case)). In case of same block for the left end, it sorts them by increasing right end. This way you'll end up with
blocks. In each block, the left pointer will move at most 
times, so you have 
(assuming Q are the number of queries). And in each block, the right pointer will be increasing, so it will move at most N times, and since there are 
blocks, you have 
here.
What it then does in lines 53-72 is simply add/remove elements as we move the pointers to one side or the other. Think of it as a segment. If you move the right side to the right or the left side to the left, you'll be adding new elements. If you, on the other hand, move the right end to the left or the left end to the right, you'll be removing elements. That's what lines 53-72 do.
thanks....i understood.......so for every problem....we have to think our own about..... (53-72) lines...
thanks..