Yet Another Problem (Codeforces 1747D)
Tags: Others, bitmasks

You are given an array $$$a$$$ of $$$n$$$ integers $$$a_1, a_2, a_3, \ldots, a_n$$$.You have to answer $$$q$$$ independent queries, each consisting of two integers $$$l$$$ and $$$r$$$.   Consider the subarray $$$a[l:r]$$$ $$$=$$$ $$$[a_l, a_{l+1}, \ldots, a_r]$$$. You can apply the following operation to the subarray any number of times (possibly zero)-   Choose two integers $$$L$$$, $$$R$$$ such that $$$l \le L \le R \le r$$$ and $$$R - L + 1$$$ is odd.  Replace each element in the subarray from $$$L$$$ to $$$R$$$ with the XOR of the elements in the subarray $$$[L, R]$$$.   The answer to the query is the minimum number of operations required to make all elements of the subarray $$$a[l:r]$$$ equal to $$$0$$$ or $$$-1$$$ if it is impossible to make all of them equal to $$$0$$$. You can find more details about XOR operation here.

Input: The first line contains two integers $$$n$$$ and $$$q$$$ $$$(1 \le n, q \le 2 \cdot 10^5)$$$  — the length of the array $$$a$$$ and the number of queries.The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(0 \le a_i \lt 2^{30})$$$  — the elements of the array $$$a$$$.The $$$i$$$-th of the next $$$q$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ $$$(1 \le l_i \le r_i \le n)$$$  — the description of the $$$i$$$-th query.

Output: For each query, output a single integer  — the answer to that query.

Note: In the first query, $$$l = 3, r = 4$$$, subarray = $$$[3, 3]$$$. We can apply operation only to the subarrays of length $$$1$$$, which won't change the array; hence it is impossible to make all elements equal to $$$0$$$.In the second query, $$$l = 4, r = 6$$$, subarray = $$$[3, 1, 2]$$$. We can choose the whole subarray $$$(L = 4, R = 6)$$$ and replace all elements by their XOR $$$(3 \oplus 1 \oplus 2) = 0$$$, making the subarray $$$[0, 0, 0]$$$.In the fifth query, $$$l = 1, r = 6$$$, subarray = $$$[3, 0, 3, 3, 1, 2]$$$. We can make the operations as follows:   Choose $$$L = 4, R = 6$$$, making the subarray $$$[3, 0, 3, 0, 0, 0]$$$.  Choose $$$L = 1, R = 5$$$, making the subarray $$$[0, 0, 0, 0, 0, 0]$$$. 

Sample Inputs:
7 6
3 0 3 3 1 2 3
3 4
4 6
3 7
5 6
1 6
2 2

Sample Outputs:
-1
1
1
-1
2
0

Solution (Python):
def solve():
    (n, q) = map(int, input().split())
    a = [int(s) for s in input().split()]
    pref_xor = [0] * (n + 1)
    cls_z = [-1] * (n + 1)
    cls_nz = [-1] * (n + 1)
    (odd, even) = (dict(), dict())
    even['0'] = 0
    for i in range(1, n + 1):
        if a[i - 1] == 0:
            cls_nz[i] = cls_nz[i - 1]
        else:
            cls_nz[i] = i
        pref_xor[i] = pref_xor[i - 1] ^ a[i - 1]
        cur = str(pref_xor[i])
        if i & 1:
            if cur in even:
                cls_z[i] = even[cur]
            odd[cur] = i
        else:
            if cur in odd:
                cls_z[i] = odd[cur]
            even[cur] = i
    ans = [0] * q
    for i in range(q):
        (l, r) = map(int, input().split())
        if pref_xor[l - 1] != pref_xor[r]:
            ans[i] = -1
        elif l > cls_nz[r]:
            ans[i] = 0
        elif (r - l + 1) % 2:
            ans[i] = 1
        elif a[l - 1] == 0 or a[r - 1] == 0:
            ans[i] = 1
        elif l <= cls_z[r]:
            ans[i] = 2
        else:
            ans[i] = -1
    print('\n'.join((str(num) for num in ans)))
t = 1
while t:
    t -= 1
    solve()

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
BUFSIZE = 8192
from bisect import bisect_right

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
sys.setrecursionlimit(100000)
t = 1
for _ in range(t):
    (n, q) = map(int, input().split())
    b = [0] + list(map(int, input().split()))
    c = []
    d = defaultdict(lambda : [])
    px = [0 for i in range(n + 1)]
    cnt = [0 for i in range(n + 1)]
    for i in range(1, n + 1):
        curr = px[i - 1] ^ b[i]
        px[i] = curr
        d[curr, i % 2].append(i)
        if b[i] != 0:
            cnt[i] = cnt[i - 1] + 1
        else:
            cnt[i] = cnt[i - 1]
    for i in range(q):
        (l, r) = map(int, input().split())
        tot = px[r] ^ px[l - 1]
        nze = cnt[r] - cnt[l - 1]
        if tot != 0:
            print(-1)
        elif (r - l) % 2 == 0:
            if nze == 0:
                print(0)
            else:
                print(1)
        elif nze == 0:
            print(0)
        elif b[l] == 0 or b[r] == 0:
            print(1)
        else:
            try:
                ne = d[px[l - 1], l % 2][bisect_right(d[px[l - 1], l % 2], l - 1)]
                if ne <= r:
                    print(2)
                else:
                    print(-1)
            except:
                print(-1)

Solution (Python):
from collections import defaultdict

def main():
    (n, q) = readIntArr()
    a = readIntArr()
    prefixsum = a.copy()
    for i in range(1, n):
        prefixsum[i] += prefixsum[i - 1]
    prefixxor = []
    x = 0
    for y in a:
        x ^= y
        prefixxor.append(x)
    xor_odd_indexes = defaultdict(lambda : [])
    xor_even_indexes = defaultdict(lambda : [])
    for (i, x) in enumerate(prefixxor):
        if i % 2 == 1:
            xor_odd_indexes[x].append(i)
        else:
            xor_even_indexes[x].append(i)
    allans = []
    for _ in range(q):
        (l, r) = readIntArr()
        l -= 1
        r -= 1
        xor = prefixxor[r]
        if l - 1 >= 0:
            xor ^= prefixxor[l - 1]
        if xor != 0:
            allans.append(-1)
            continue
        total = prefixsum[r]
        if l - 1 >= 0:
            total -= prefixsum[l - 1]
        if total == 0:
            allans.append(0)
            continue
        if (r - l + 1) % 2 == 1:
            allans.append(1)
            continue
        elif a[l] == 0 or a[r] == 0:
            allans.append(1)
            continue
        if l - 1 >= 0:
            xor1 = prefixxor[l - 1]
        else:
            xor1 = 0
        if l % 2 == 1:
            arr = xor_odd_indexes[xor1]
        else:
            arr = xor_even_indexes[xor1]
        m = len(arr)
        (lo, hi) = (-1, m - 1)
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if arr[mid] < l:
                lo = mid
            else:
                hi = mid - 1
        if lo + 1 < m and arr[lo + 1] <= r:
            ans = 2
        else:
            ans = -1
        allans.append(ans)
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()