Mo's Algorithm: left and right limit movement

Revision en1, by decoder123, 2016-01-26 13:15:48

In the last Div-2 Contest Div2E can be solved using MO's sqrt decomposition.

I couldn't solve the problem that day. I read the editorial and understood it.

The thing left to do is to implement it.

While implementing I realized the most difficult part of the algorithm (or as it seems to me!). And it 2 things:-

a) The intilization of Mo's left and Mo's right .(ML and MR) respectively. b) Movement of them.

Now I couldn't get correct answer even for the given test cases in my computer. So I move to see the code.: There are 2 ways people solved the problem:-

a) some of the coders initiliazed ML=1,MR=0. and then go on adding and removing as required. b) some initialized ML=0,MR=0 but cnt[0]=1..(occurences of 0 is 1) and then solved it.

Then I observed that no movement of pointers are different.

End result: I am utterly confused. My question is

  1. For query [l,r] we have to be sure that pref[l-1] to pref[r] must be present in this problem. Now how can I write the code keeping in mind the range and should I follow 0 based or 1 based. How to do this? Is there any idea/trick/concept that will clear this MO's pointer movement?

Can someone provide a general idea on left and right pointer movement? (post incremment ,pre increment,..,initialization whole thing made me confuse..I am trying for 3 hours...reading the tutorials..but I can't write the code for pointer movement on my own..)


Note: Somebody please explain to me. No matter how dumb this question sounds to you.


  Rev. Lang. By When Δ Comment
en1 English decoder123 2016-01-26 13:15:48 1635 Initial revision (published)