PROBLEM LINK:Author: Yogendra Bhanu Singh PROBLEMYou have an array of $N$ elements and 2 types of queries:
QUICK EXPLANATIONReplace the array by its prefix xors array. The queries became as follows: xor the suffix of the array with some value and find how many indexes less than a given one have a value equal to the some other given value. For doing this split the array into blocks of size $O(\sqrt N)$ and perform queries over the blocks. EXPLANATION0indexation is used in the editorial. Symbol $\oplus$ means bitwise xor. Denote $p[i]$ as bitwise xor of the first $i$ elements of the array, i.e. $p[i] = a_0$ $\oplus$ $a_1$ $\oplus$ $\dots$ $\oplus$ $a_i$. $p[i]$ is called prefix xors sums array of the array $a$ and can be calculated in $O(n)$ time using the fact $p[i] = p[i – 1] \oplus a[i]$ for $i \geq 1$. Replace array $a$ with it’s prefix xor array $p$ and perform queries over the array $p$, not $a$. Suppose it’s need to perform a query of the second type, i.e. find the amount of prefixes of the array $a$ with its length no more than $k$ with xor on it equal to a given $x$. It’s obvious such a query in the array $a$ is equal to a query “how many numbers on the prefix with length $k$ are equal to a given $x$” in the array $p$. If we need to perform a query of the first type it's need to recalculate the array $p$. Suppose it’s required to change value at the position $i$ in $a$ to $x$. Let’s understand how the array $p$ changes. For any $j < i$ $p[j]$ doesn’t change since the $i$th element doesn’t affect to the prefixes before position $i$. In the same time for any $j \geq i$ old value of $a[i]$ doesn’t affect on $p[j]$ anymore, so it’s need to “cancel” its contribution in $p[j]$. Since $x$ $\oplus$ $x$ = $0$ for any $x$ we can do $p[j] = p[j]$ $\oplus$ $a[i]$, thereby saying that an old value of $a[i]$ is not affecting on $p[j]$ anymore. After that do $p[j] = p[j]$ $\oplus$ $x$ meaning we add $x$ to $p[j]$. Therefore, for changing value at position $i$ in array $a$ it’s need to do $p[j] = p[j]$ $\oplus$ $c$ for each $j \geq i$, where $c = x$ $\oplus$ $a[i]$. So queries became as follows:
It can be done using sqrtdecomposition. Split the array $p$ into blocks with $B$ = length of the each block. It means elements of the array with indexes $[0; B1]$ belong to the block with index $0$, elements with indexes $[B; 2B1]$ belong to the block with index $1$ and so on, elements with indexes $[\frac{N1}{B} \cdot B, N1]$ belong to the last block (it can contain less than $B$ elements). It’s obvious there are $O(\frac{N}{B})$ such blocks. It’s easy to see any index $i$ belongs to the block with index $\frac{i}{B}$. For each block $i$ store an additional value $t[i]$ meaning each value inside this block is xorred with $t[i]$ ($t[i] = 0$ initially), i.e equal to $a[j]$ $\oplus$ $t[i]$. In other words, for each index $j$ of the array, the actual value of $j$th prefix xor sum is $p[j]$ $\oplus$ $t[\frac{j}{B}]$. Also each block stores an array $freq[i][j]$ meaning how many values of $p$ equal to $j$ belong to it. Before performing the queries calculate the array freq, just increasing $freq[\frac{i}{B}][p[i]]$ by $1$ for each $i$. Now suppose query of the first type comes. Suppose index $i$ belongs to the $k = \frac{i}{B}$th block. Set $c$ to $a[i] \oplus x$ and $a[i]$ to x. Then for any index $j$ after $i$ in the $k$th block $p[j]$ should be changed to $p[j]$ $\oplus$ $c$. Just iterate over all such $j$’s and decrease $freq[k][p[j]]$ by $1$, increase $freq[k][p[j]$ $\oplus$ $c]$ by $1$ and do $p[j] = p[j]$ $\oplus$ $c$. In this way we updated the information in the $k$th block in $O(B)$ time. For any block with index $p > k$ we can’t update each index independently because it’s slow, but we can simply change $t[p]$ to $t[p]$ $\oplus$ $c$ “promising” to xor it with $c$ after, when answering the queries of the second type. For answering a query suppose $i$ belongs to the $k=\frac{i}{B}$th block. Then it's need to check each index $j$ before $i$ inside this block. Just iterate over $j$ from the beginning of the $k$th block to $i$ and increase the answer if $p[j]$ $\oplus$ $t[\frac{j}{B}]$ is equal to $x$ from the query. For each block $p$ before $k$, we know the frequency of each value inside it. So we can just add to the answer $freq[p][x]$, but remembering about extra xors it turns into $freq[p][x$ $\oplus$ $t[p]]$. In each query we iterate over $O(\frac{N}{B})$ blocks and one whole block taking $O(B)$ time for it. So each query takes $O(B + \frac{N}{B})$ time. Taking $B = \sqrt N$ leads to the optimal $O(\sqrt N)$ time per query, so the array should be splitted into blocks of size around $\sqrt N$. Total time complexity is $O(Q \sqrt N)$. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 13 Dec '17, 03:11

I'm a bit confused. When answering the query 2; if you do not update the frequency table for the updated value. Won't they have invalid values, am i missing something? When we performed operation 1, we did not update frequency values of the remaining blocks. Won't the value inside them, which has count of xors from previous values become invalid? answered 16 Dec '17, 16:56

no,for "other blocks",you have to maintain a lazy array which will be keeping the track that before answering a query ,you are supposed to look for its update in the lazy array and count your no of required values accordingly... answered 17 Dec '17, 18:50

Didn't know that we could allocate upto 2 gb memory. thats why I didn't think of sqareroot decomposition with storing frequency. answered 17 Dec '17, 20:42

why we can't use segmenttree for this problem?? m getting TLE in last subtask ? thanku inadvance! answered 26 Dec '17, 14:20

Why this code is giving WA on a single test case of subtask 4 : https://www.codechef.com/viewsolution/16702764 answered 30 Dec '17, 17:59

Can we solve this problem using Segment Tree also? Or it Would get TLE? answered 13 Dec '18, 20:04

The latex seems to be messed up for no reason for this post. Asked @admin to give it a look.