Changing Array
Contest: Mail.Ru Cup 2018 Round 1
Difficulty rating: 1900
Tags: greedy, implementation

At a break Vanya came to the class and saw an array of $$$n$$$ $$$k$$$-bit integers $$$a_1, a_2, \ldots, a_n$$$ on the board. An integer $$$x$$$ is called a $$$k$$$-bit integer if $$$0 \leq x \leq 2^k - 1$$$.

Of course, Vanya was not able to resist and started changing the numbers written on the board. To ensure that no one will note anything, Vanya allowed himself to make only one type of changes: choose an index of the array $$$i$$$ ($$$1 \leq i \leq n$$$) and replace the number $$$a_i$$$ with the number $$$\overline{a_i}$$$. We define $$$\overline{x}$$$ for a $$$k$$$-bit integer $$$x$$$ as the $$$k$$$-bit integer such that all its $$$k$$$ bits differ from the corresponding bits of $$$x$$$.

Vanya does not like the number $$$0$$$. Therefore, he likes such segments $$$[l, r]$$$ ($$$1 \leq l \leq r \leq n$$$) such that $$$a_l \oplus a_{l+1} \oplus \ldots \oplus a_r \neq 0$$$, where $$$\oplus$$$ denotes the bitwise XOR operation. Determine the maximum number of segments he likes Vanya can get applying zero or more operations described above.

Input format:
The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 200\,000$$$, $$$1 \leq k \leq 30$$$).

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 2^k - 1$$$), separated by spaces — the array of $$$k$$$-bit integers.

Output format:
Print one integer — the maximum possible number of segments with XOR not equal to $$$0$$$ that can be obtained by making several (possibly $$$0$$$) operations described in the statement.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example if Vasya does not perform any operations, he gets an array that has $$$5$$$ segments that Vanya likes. If he performs the operation with $$$i = 2$$$, he gets an array $$$[1, 0, 0]$$$, because $$$\overline{3} = 0$$$ when $$$k = 2$$$. This array has $$$3$$$ segments that Vanya likes. Also, to get an array with $$$5$$$ segments that Vanya likes, he can perform two operations with $$$i = 3$$$ and with $$$i = 2$$$. He then gets an array $$$[1, 0, 3]$$$. It can be proven that he can't obtain $$$6$$$ or more segments that he likes.

In the second example, to get $$$19$$$ segments that Vanya likes, he can perform $$$4$$$ operations with $$$i = 3$$$, $$$i = 4$$$, $$$i = 5$$$, $$$i = 6$$$ and get an array $$$[1, 4, 3, 0, 4, 3]$$$.

Example input:
3 2
1 3 0

Example output:
5

Example input:
6 3
1 4 4 7 3 4

Example output:
19

Editorial:
We need to maximize the number of segments with XOR-sum of its elements not equal to $$$0$$$. Let's note that the total number of segments is $$${n+1 \choose 2} = n \cdot (n + 1) / 2$$$ so we need to minimize the number of segments with XOR-sum of its elements equal to $$$0$$$. Let's call such segments bad.
Consider the prefix XOR sums of array $$$a$$$. Let's define $$$p_i = a_1 \oplus \dots \oplus a_i$$$ for any $$$0 \leq i \leq n$$$. Note that the segment $$$[l, r]$$$ is bad if $$$pr_{l-1} = pr_r$$$.
How does an array $$$p$$$ changes in a single operation with an array $$$a$$$? Let's note that $$$\overline{x} = x \oplus (2^k - 1)$$$. If we do operation with the element $$$i$$$ then in array $$$p$$$ all elements $$$p_j$$$ ($$$j \geq i$$$) will change to $$$p_j \oplus (2^k - 1)$$$ or $$$\overline{p_j}$$$. So after all operations, element of $$$p$$$ will be either equal to itself before operations or will be equal to itself before operations but with all changed bits. But $$$p_0=0$$$ still.
On the other hand. Suppose that there are some changes of this kind in the array $$$p$$$. Let's prove that we could make some operations in the array $$$a$$$ so that $$$p$$$ will be changed and became exactly the same. To prove this, note that $$$a_i = p_{i-1} \oplus p_i$$$, so all values of $$$a_i$$$ have either not changed or have changed to numbers with all changed bits. So let's just assume that we are changing the array $$$p$$$ (all its elements except the element with index $$$0$$$), not the array $$$a$$$.
Let's note that two numbers $$$x$$$ and $$$y$$$ can become equal after all operations with them if they are equal or $$$x = \overline{y}$$$. So we can replace $$$p_i$$$ with $$$min(p_i, \overline{p_i})$$$ for any $$$i$$$ in the array $$$p$$$. The answer will be the same if we do this. But it will be impossible to get equal numbers from different numbers in the new array.
Let's calculate for each number $$$c$$$ the number of its occurrences in the array $$$p$$$ and denote it for $$$k$$$. Some of this $$$k$$$ numbers we can leave equal to $$$c$$$, and some of them we change to $$$\overline{c}$$$. Let's change $$$0 \leq a \leq k$$$ numbers. Then we want to minimize the number of pairs of equal numbers, which is $$${k-a+1 \choose 2} + {a+1 \choose 2}$$$. To do this, we need to change and not change the approximately equal number of numbers, that is, the minimum is reached at $$$a = \lfloor k / 2 \rfloor$$$. It can be proved simply. So we should divide the numbers this way for any $$$c$$$ and sum the answers.
For each number $$$c$$$, the number of its occurrences in the array can be calculated using the sorting algorithm or the std::map structure into the C++ language.
Time complexity: $$$O(n \cdot log (n))$$$.