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 .(
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
cnt=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
- For query
[l,r]we have to be sure that
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.