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

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

Thanks.

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

There are different ways to implement it. I maintained half-closed interval [l, r). So initially l = 0, r = 0 — empty interval. You can see my submission

res -= cnt[pref[l] ^ k] — (k == 0); What is the meaning of this line? (if k is 0 then we have to add 1 to result..why?)

Here we want to delete all x in range [l + 1, r) such that k == pref[l] ^ pref[x]. If k == 0 then pref[l] == pref[x]. So we shouldn't consider this number (because it's not in range [l + 1, r)).

PS: It makes more sense to change

to

Lets q[] be your queries. Then you can set MS=q[0].left and MR=q[0].right. Then you just need one extra loop before the main MO's algorithm part that add all numbers in [ML; MR]. You can look at one of my last submission.

PS:Here's a linkOkay! so if we add the first query ..the elements required in the query. Then everything becomes easy and from the next query you just ad or delete the elements. This can relieve us from thinking about initialization part.

Can we apply this in any sqrt-decomposition problem? (which can be solved using MO actually)

Here's how it worked down for me as I was too trying the same for past few hours(opening everybody's code and trying to get that how did pointer movement actually worked out.)

Let's suppose , for range [L,R] we have what is the answer up till now and

`cnt[i]`

stores what is the number of times that`i XOR`

has occurred in current range.I am taking closed interval

`[L,R]`

means for the current range we have all the XOR prefixes included from`prefix[L-1]`

to`prefix[R]`

(assuming 1 indexed).Now , considering the reason for

`cnt[0] = 1`

that you mentioned above.Suppose , you have this as test case.

1 1 1

1

1 1

So, while moving your pointer towards right you will add

`current_answer += cnt[K ^ prefix[currR]];`

and since`K ^ prefix[currR]`

(for currR = 1) = 0 , so the correct answer upto this state must come equal to 1. (Thus , it is marked initially by some people as cnt[0] = 1) .What if we don't actually want to avoid this ? Just start your

`currR`

pointer from a step back.Now , considering four conditions for MO's algoithm.

`int currL = 1 ,currR = 0 ; int L = query[i].L ; int R = query[i].R ;`

Finally , that crooked up my mind is what is the need for including the

`prefix[L-1] to prefix[R]`

is:Suppose you move your right pointer towards right. Now , your current answer would modify as adding of new sub arrays that end at this current right position .

So, let's suppose that you are searching for

`index`

such that`a[index] ^ a[index+1] .. ^ a[R]`

= K for the current window which is basically searching for position such that`prefix[R] ^ prefix[position] = K`

and`index`

can thus start from`position+1`

.Eventually it means, you want to count all the

`XOR'S = prefix[position]`

so that`a[position+1] ^ a[position+2] .. ^ a[R] = K`

. Thus, minimum value of`position+1`

can be`L`

,hence`position must be L-1`

. Thus there's a need to include prefixes from`[L-1] to [R]`

.Here's my submission.

Happy Coding :)

Yes, the part before you started using curR a step back (from 0) , you are using the initialization

`curR=1`

and`curL=1`

. right?Second thing,

`cnt[0]=1`

, chances that this idea occurs on an ongoing contest is less likely for me. Is there any drawback in looping for the first interval and then apply MO's correctly?Yes,

When I say just start a step back , I mean to say that

`currL=1 , currR = 0`

in the beginning and now start the process for MO's algorithm .If you do so , then there is no need to include the case of

`cnt[0] = 1`

. Because, when`currR < R`

for the first time in the first loop among four, you would already make`cnt[0]=1`

.For a better understanding, make a dry run :)

EDIT : No, there is no problem in making the loop for the first query, and then apply MO's algorithm , just be careful that after the first query , you have included all the prefixes from

`[L-1] to [R]`

and you have the current answer from`[L] to [R]`

.There is one thing though in the looping solution..Have you seen the code the previous user radoslav11 posted? I mean in that solution

`[l,r]--->[l-1,r]`

is converted . Then they will be added.Now in this case suppose

`[1,4]`

is given then`[0,4]`

will be conidered range. Then pref[0] will be added in the MO's structure.But pref[0] is initially 0..`cnt[0]++;`

that is`cnt[0]=1;`

so that will be 1..I don't know if people considers these small facts that doesn't affects the solution but they are happening, we can't ignore them.

It all depends on your pointer movement handling. Either you want them to be 1-indexed or 0-indexed.

User radoslav11 has considered it

`0-indexed`

and storing Xor's`1-indexed.`

Thus xor[0] = 0.So, it's the same thing .

yes, so for

`[1,5]`

query we will consider`[0,5]`

right? Then if this is the 1st query what happens..it will add`pref[0]=0,`

`pref[1]=.`

. .`pref[5]=`

right? WHat does adding mean? Adding with the answer the number of occurence of`[target^value].`

and then increasing

`cnt[value]`

. so in this case value=0`cnt[0]=1`

intially..I am asking about this..why isn't this a problem? I mean we are increasing a value by 1 without any intention of doing so!!So look:

You have an subarray[L; R]

To find it's Xor you need the Xor of first L-1 elements and Xor of the first R elememts (lets call them pref[L-1] and pref[R]).

Now lets look at the same problem but where the quert was:

Query L, R: check if Xor of elements is equal to K

The solution is simple: just find the xor of the array = pref[l-1]^pref[r] and check if its equal to K.

For that we use MO's algorithm.

You can asume that the "window" in the algorithm is a set of integers.

In our case we need to find the number of pairs in pref[L-1; R] such that their xor is equal to K.

That means that we dont really have to store the current list of integers in the "window" but we can simply store the count.

Then when we add something what happens?

We see how many integers in our "window" xor the number we add are equal to K. This is equal to the number of occurrences of the current number we add xor K.

The delete is similar but we dont inrease our answer but decrease.

So this is the solution to this task using MO's algo.