Hi codeforces, recently I have came across an interesting problem : https://codeforces.com/problemset/problem/617/E. I had a rough time trying to understand the solution of this problem even after i read the tutorial. Basically I can't see why the add() and del() function work because of my lack of knowledges about the XOR operation. Now after a few hours of thinking, I have officially surrendered ... That's why I'm here, asking for an explanation.
P/S : I'm just dumb, especially when it come to math and other similar stuff. Pls don't be to harsh on me ... And just in case, I'm talking about the add() and del() function in the solution. You will find it in the editorial (of course)
Edit : Just in case, I can't seem to understand why adding cnt[favourite ^ v] help me count the number of pair i, j that satisfies l ≤ i ≤ j ≤ r and the xor of the numbers ai, ai + 1, ..., aj is equal to k (favourite).
The most important fact is a ^ b ^ b = a. What can we get from it?
If we know a ^ b and b we can recover a. That's why prefix XORs are possible. (Some operations are impossible like min/max, gcd/lcm because we can't recover a. For them we must use more complicated data structures like sparse table).
Only numbers those appear even number of times matter in an expression with XOR. In this problem we add one occurrence of each number to invert this fact. (Additional facts to understand it: a ^ a = 0, a ^ 0 = a).
Also this might be useful for XOR problems:
For each enabled bit of b, invert it in a. So ^ 1 inverts the last bit, ^ 2 inverts the bit before the last, ^ 4 inverts the third bit from the end and so on.
Well, ok, now I understood how did the prefix array work on XOR. Thank you for that. But the main thing remain unsolved : How do i count the number of interval i, j that XOR a[i] -> a[j] == k ? If i'm paying attention to numbers those appear even number of time, i can basically don't care about them anymore, but how to i process further with the remaining ? I knew that i can calculate XOR l, r in O(1), but i will a faster way to check these pairs, otherwise it would be a TLE for me, which is a sad ending ... And i'm using Mo's algorithm, with a complexity of O((N+Q) * sqrt(N)), so i need to check each time i move the border in O(1) ...
Fact 1 covers that too. pref[r] ^ pref[l] = k, then pref[r] ^ k = pref[l]. Now just use a cnt array for pref values to count possible l-s and r-s.