PROBLEM LINK:
Author: Yogendra Bhanu Singh
Tester: Mugurel Ionut Andreica
Editorialist: Kirill Gulin
PROBLEM
You have an array of N elements and 2 types of queries:
- Given two numbers i and x, the value at index i should be updated to x.
- Given two numbers i and k, your program should output the total number of prefixes of the array with the last index \leq i in which the xor of all elements is equal to k.
QUICK EXPLANATION
Replace 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.
EXPLANATION
0-indexation 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:
- Given i and x, do p[j] = p[j] \oplus c for each j \geq i, where c = a[i] \oplus x.
- Find the amount of such $i$’s that i \leq k and p[i] = x with given k and x.
It can be done using sqrt-decomposition. Split the array p into blocks with B = length of the each block. It means elements of the array with indexes [0; B-1] belong to the block with index 0, elements with indexes [B; 2B-1] belong to the block with index 1 and so on, elements with indexes [\frac{N-1}{B} \cdot B, N-1] 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.
Tester’s solution can be found here.