hello_its_me's blog

Need help with a mo's algorithm problem
By hello_its_me, 14 months ago, In English

this is the problem — https://mirror.codeforces.com/contest/617/problem/E

I can't understand the solution. What is cnt[v] actually storing here and how are we getting the ans with simply cnt[v xor k] for one shifting of bounds in O(1) time ?

Thanks in advance.

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
14 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

In Mo's algorithm, we either increase one of the ends, or decrease one of the ends. Both ways, we are interested in counting how many intervals there are in the L-R range with xor sum equal to k. If we take prefix xor sums, we can write this as pref[R+1] ^ pref[i] == k ==> pref[i] == k ^ pref[R+1]. Therefore, we need to maintain counts of all possible values of pref[i] in the interval, so that we can update the answer. Since each time L or R changes, one value of pref[i] gets inserted or removed, we can do this in O(1).

→ Reply