vsanjay_nitdgp's blog

MO ALGO
By vsanjay_nitdgp, history, 9 years ago, In English

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....

http://ideone.com/8qZj1Z

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..

  • Vote: I like it
  • -8
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    thanks....i understood.......so for every problem....we have to think our own about..... (53-72) lines...

    thanks..

    → Reply