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