Vasya and Good Sequences
Contest: Technocup 2019 - Elimination Round 1
Difficulty rating: 2000
Tags: bitmasks, dp

Vasya has a sequence $$$a$$$ consisting of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$. Vasya may pefrom the following operation: choose some number from the sequence and swap any pair of bits in its binary representation. For example, Vasya can transform number $$$6$$$ $$$(\dots 00000000110_2)$$$ into $$$3$$$ $$$(\dots 00000000011_2)$$$, $$$12$$$ $$$(\dots 000000001100_2)$$$, $$$1026$$$ $$$(\dots 10000000010_2)$$$ and many others. Vasya can use this operation any (possibly zero) number of times on any number from the sequence.

Vasya names a sequence as good one, if, using operation mentioned above, he can obtain the sequence with bitwise exclusive or of all elements equal to $$$0$$$.

For the given sequence $$$a_1, a_2, \ldots, a_n$$$ Vasya'd like to calculate number of integer pairs $$$(l, r)$$$ such that $$$1 \le l \le r \le n$$$ and sequence $$$a_l, a_{l + 1}, \dots, a_r$$$ is good.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — length of the sequence.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{18}$$$) — the sequence $$$a$$$.

Output format:
Print one integer — the number of pairs $$$(l, r)$$$ such that $$$1 \le l \le r \le n$$$ and the sequence $$$a_l, a_{l + 1}, \dots, a_r$$$ is good.

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

Note:
In the first example pairs $$$(2, 3)$$$ and $$$(1, 3)$$$ are valid. Pair $$$(2, 3)$$$ is valid since $$$a_2 = 7 \rightarrow 11$$$, $$$a_3 = 14 \rightarrow 11$$$ and $$$11 \oplus 11 = 0$$$, where $$$\oplus$$$ — bitwise exclusive or. Pair $$$(1, 3)$$$ is valid since $$$a_1 = 6 \rightarrow 3$$$, $$$a_2 = 7 \rightarrow 13$$$, $$$a_3 = 14 \rightarrow 14$$$ and $$$3 \oplus 13 \oplus 14 = 0$$$.

In the second example pairs $$$(1, 2)$$$, $$$(2, 3)$$$, $$$(3, 4)$$$ and $$$(1, 4)$$$ are valid.

Example input:
3
6 7 14

Example output:
2

Example input:
4
1 2 1 16

Example output:
4

Editorial:
Since we can swap any pair of bits in the number, so all we need to know is just the number of ones in its binary representation. Let create array $$$b_1, b_2, \dots , b_n$$$, where $$$b_i$$$ is number of ones in binary representation of $$$a_i$$$. Forget about array $$$a$$$, we will work with array $$$b$$$.
Let's find a way to decide whether fixed segment is good or not. It can be proven that two conditions must be met. At first, sum of $$$b_i$$$ at this segment should be even. At second, maximal element should be lower or equal to the sum of all other elements.
We will iterate over left borders of subsegments in descending order and for each left border $$$l$$$ calculate number of right borders $$$r$$$ such that $$$[l, r]$$$ is good.
Let's, as first, "forget" about condition on maximum and calculate $$$cntAll(l)$$$ — number of right borders $$$r$$$, such that sum on segment $$$[l,r]$$$ is even and left border $$$l$$$ is fixed. We can calculate it by counting $$$S_0$$$ and $$$S_1$$$ — the number of suffixes of array with even sum of $$$b_i$$$ and number of suffixes with odd sum. If the current sum $$$\sum\limits_{i=l}^{n}{b_i}$$$ is even then $$$cntAll(l) = S_0$$$ since $$$\sum\limits_{i=l}^{r}{b_i} = \sum\limits_{i=l}^{n}{b_i} - \sum\limits_{i=r+1}^{n}{b_i}$$$. If $$$\sum\limits_{i=l}^{n}{b_i}$$$ is odd then $$$cntAll(l) = S_1$$$.
Since we forgot about condition on maximum, some bad segments were counted. Since $$$a_i \le 10^{18}$$$ then $$$b_i < 61$$$. That's why if length of the segment $$$\ge 61$$$, condition on the maximum is always true. So, for a fixed $$$l$$$ we can iterate over all right borders in the $$$[l, l + 61]$$$ and subtract number of segments with even sum and too large maximum (since these segments were counted in the answer).