Vasya and Good Sequences (Codeforces 1058E)
Tags: DP, brute force

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

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.

Sample Inputs:
3
6 7 14

4
1 2 1 16

Sample Outputs:
2

4

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

def cal(x):
    tot = 0
    while x:
        if x & 1:
            tot += 1
        x >>= 1
    return tot
sum = []
even = [0]
odd = [0]
b = [0]
last = 0
for i in a:
    b.append(cal(i))
for i in b:
    last += i
    sum.append(last)
for i in range(1, len(a) + 1):
    if sum[i] & 1:
        odd.append(odd[-1] + 1)
        even.append(even[-1])
    else:
        odd.append(odd[-1])
        even.append(even[-1] + 1)
ans = 0
for i in range(len(a) + 1):
    if sum[i] & 1:
        tot = odd[len(a)] - odd[i]
        mx = 0
        for j in range(i + 1, min(i + 65, len(a) + 1)):
            mx = max(mx, b[j])
            if mx * 2 > sum[j] - sum[i] and sum[j] - sum[i] & 1 == 0:
                tot -= 1
        ans += tot
    else:
        tot = even[len(a)] - even[i]
        mx = 0
        for j in range(i + 1, min(i + 65, len(a) + 1)):
            mx = max(mx, b[j])
            if mx * 2 > sum[j] - sum[i] and sum[j] - sum[i] & 1 == 0:
                tot -= 1
        ans += tot
print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.buffer.readline().decode().strip()
get_bit = lambda x, i: x >> i & 1
(n, a) = (int(input()), [sum([get_bit(int(x), j) for j in range(60)]) for x in input().split()])
(su, o) = (a[0], 0)
for i in range(1, n):
    su += a[i]
    o += su & 1
(ans, parity, e, su) = (0, 0, n - 1 - o, a[0])
for i in range(n - 1):
    su += a[i + 1]
    if parity == 0:
        ans += e
    else:
        ans += o
    parity ^= a[i] & 1
    if su & 1:
        o -= 1
    else:
        e -= 1
    ma = su2 = a[i]
    for j in range(i + 1, min(n, i + 60)):
        (ma, su2) = (max(ma, a[j]), su2 + a[j])
        ans -= su2 - ma < ma and su2 & 1 == 0
print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.buffer.readline().decode().strip()
get_bit = lambda x, i: x >> i & 1
(n, a) = (int(input()), [sum([get_bit(int(x), j) for j in range(60)]) for x in input().split()])
(pre, o) = ([a[0]], 0)
for i in range(1, n):
    pre.append(pre[-1] + a[i])
    o += pre[i] & 1
(ans, parity, e) = (0, 0, n - 1 - o)
for i in range(n - 1):
    if parity == 0:
        ans += e
    else:
        ans += o
    parity ^= a[i] & 1
    if pre[i + 1] & 1:
        o -= 1
    else:
        e -= 1
    ma = su = a[i]
    for j in range(i + 1, min(n, i + 60)):
        (ma, su) = (max(ma, a[j]), su + a[j])
        ans -= su - ma < ma and su & 1 == 0
print(ans)