Beautiful Subarrays (Codeforces 665E)
Tags: Others, divide and conquer

One day, ZS the Coder wrote down an array of integers a with elements a1,  a2,  ...,  an.A subarray of the array a is a sequence al,  al  +  1,  ...,  ar for some integers (l,  r) such that 1  ≤  l  ≤  r  ≤  n. ZS the Coder thinks that a subarray of a is beautiful if the bitwise xor of all the elements in the subarray is at least k.Help ZS the Coder find the number of beautiful subarrays of a!

Input: The first line contains two integers n and k (1 ≤ n ≤ 106, 1 ≤ k ≤ 109) — the number of elements in the array a and the value of the parameter k.The second line contains n integers ai (0 ≤ ai ≤ 109) — the elements of the array a.

Output: Print the only integer c — the number of beautiful subarrays of the array a.


Sample Inputs:
3 1
1 2 3

3 2
1 2 3

3 3
1 2 3

Sample Outputs:
5

3

2

Solution (Python):
(size, next_i) = (2 * 10 ** 7, 1)
(size_0, size_1) = ([0] * size, [0] * size)
(next_0, next_1) = ([-1] * size, [-1] * size)

def insert(i, bit, d):
    global size, next_i
    digit = 1 << d
    while digit > 1:
        b = 1 if bit & digit else 0
        if (next_1 if b else next_0)[i] == -1:
            (next_1 if b else next_0)[i] = next_i
            next_i += 1
        (size_1 if b else size_0)[i] += 1
        i = (next_1 if b else next_0)[i]
        digit >>= 1
    (size_1 if bit & 1 else size_0)[i] += 1
if __name__ == '__main__':
    import sys
    (n, k) = map(int, sys.stdin.buffer.readline().decode('utf-8').split())
    a = list(map(int, sys.stdin.buffer.readline().decode('utf-8').split()))
    insert(0, 0, 29)
    (acc, ans) = (0, 0)
    for x in a:
        i = 0
        acc ^= x
        digit = 1 << 29
        (mask, req) = (0, 0)
        while digit and i != -1:
            mask |= digit
            if (acc ^ req) & mask | digit >= k:
                ans += (size_0 if acc & digit else size_1)[i]
                i = (next_1 if acc & digit else next_0)[i]
                req |= acc & digit
            else:
                i = (next_0 if acc & digit else next_1)[i]
                req |= acc & digit ^ digit
            digit >>= 1
        insert(0, acc, 29)
    print(ans)

Solution (Python):
(size, next_i) = (2 * 10 ** 7, 1)
(size_0, size_1) = ([0] * size, [0] * size)
(next_0, next_1) = ([-1] * size, [-1] * size)

def insert(i, bit, d):
    global size, next_i
    digit = 1 << d
    while digit > 1:
        b = 1 if bit & digit else 0
        if (next_1 if b else next_0)[i] == -1:
            (next_1 if b else next_0)[i] = next_i
            next_i += 1
        (size_1 if b else size_0)[i] += 1
        i = (next_1 if b else next_0)[i]
        digit >>= 1
    (size_1 if bit & 1 else size_0)[i] += 1
if __name__ == '__main__':
    import sys
    (n, k) = map(int, sys.stdin.buffer.readline().decode('utf-8').split())
    a = list(map(int, sys.stdin.buffer.readline().decode('utf-8').split()))
    insert(0, 0, 29)
    (acc, ans) = (0, 0)
    for x in a:
        i = 0
        acc ^= x
        digit = 1 << 29
        (mask, req) = (0, 0)
        while digit and i != -1:
            mask |= digit
            if (acc ^ req) & mask | digit >= k:
                ans += (size_0 if acc & digit else size_1)[i]
                i = (next_1 if acc & digit else next_0)[i]
                req |= acc & digit
            else:
                i = (next_0 if acc & digit else next_1)[i]
                req |= acc & digit ^ digit
            digit >>= 1
        insert(0, acc, 29)
    print(ans)

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def binary_trie(l):
    (G0, G1, cnt) = ([-1] * (l * n + 5), [-1] * (l * n + 5), [0] * (l * n + 5))
    la = 0
    return (G0, G1, cnt, l, la)

def insert(x, la):
    j = 0
    for i in range(l, -1, -1):
        cnt[j] += 1
        if x & pow2[i]:
            if G1[j] == -1:
                la += 1
                G1[j] = la
            j = G1[j]
        else:
            if G0[j] == -1:
                la += 1
                G0[j] = la
            j = G0[j]
    cnt[j] += 1
    return la

def erase(x):
    j = 0
    for i in range(l, -1, -1):
        cnt[j] -= 1
        if x & pow2[i]:
            j = G1[j]
        else:
            j = G0[j]
    cnt[j] -= 1
    return

def xor_and_count_max(x, k):
    j = 0
    ans = 0
    for i in range(l, -1, -1):
        if not x & pow2[i]:
            if not k & pow2[i]:
                if G1[j] ^ -1:
                    ans += cnt[G1[j]]
                j = G0[j]
            else:
                j = G1[j]
        elif not k & pow2[i]:
            if G0[j] ^ -1:
                ans += cnt[G0[j]]
            j = G1[j]
        else:
            j = G0[j]
    return ans
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
pow2 = [1]
for _ in range(30):
    pow2.append(2 * pow2[-1])
(G0, G1, cnt, l, la) = binary_trie(30)
b = list(a)
for i in range(n - 2, -1, -1):
    b[i] ^= b[i + 1]
(ans1, ans2) = (0, 0)
mod = pow(10, 9) + 7
for (i, j) in zip(a, b):
    la = insert(j, la)
    ans1 += xor_and_count_max(i ^ j, k - 1)
    ans2 += ans1 // mod
    ans1 %= mod
ans = ans1 + ans2 * mod
print(ans)