Data Structures Fan (Codeforces 1872E)
Tags: DP, bitmasks

You are given an array of integers $$$a_1, a_2, \ldots, a_n$$$, as well as a binary string$$$^{\dagger}$$$ $$$s$$$ consisting of $$$n$$$ characters.Augustin is a big fan of data structures. Therefore, he asked you to implement a data structure that can answer $$$q$$$ queries. There are two types of queries: "1 $$$l$$$ $$$r$$$" ($$$1\le l \le r \le n$$$) — replace each character $$$s_i$$$ for $$$l \le i \le r$$$ with its opposite. That is, replace all $$$\texttt{0}$$$ with $$$\texttt{1}$$$ and all $$$\texttt{1}$$$ with $$$\texttt{0}$$$. "2 $$$g$$$" ($$$g \in \{0, 1\}$$$) — calculate the value of the bitwise XOR of the numbers $$$a_i$$$ for all indices $$$i$$$ such that $$$s_i = g$$$. Note that the $$$\operatorname{XOR}$$$ of an empty set of numbers is considered to be equal to $$$0$$$.Please help Augustin to answer all the queries!For example, if $$$n = 4$$$, $$$a = [1, 2, 3, 6]$$$, $$$s = \texttt{1001}$$$, consider the following series of queries: "2 $$$0$$$" — we are interested in the indices $$$i$$$ for which $$$s_i = \tt{0}$$$, since $$$s = \tt{1001}$$$, these are the indices $$$2$$$ and $$$3$$$, so the answer to the query will be $$$a_2 \oplus a_3 = 2 \oplus 3 = 1$$$. "1 $$$1$$$ $$$3$$$" — we need to replace the characters $$$s_1, s_2, s_3$$$ with their opposites, so before the query $$$s = \tt{1001}$$$, and after the query: $$$s = \tt{0111}$$$. "2 $$$1$$$" — we are interested in the indices $$$i$$$ for which $$$s_i = \tt{1}$$$, since $$$s = \tt{0111}$$$, these are the indices $$$2$$$, $$$3$$$, and $$$4$$$, so the answer to the query will be $$$a_2 \oplus a_3 \oplus a_4 = 2 \oplus 3 \oplus 6 = 7$$$. "1 $$$2$$$ $$$4$$$" — $$$s = \tt{0111}$$$ $$$\to$$$ $$$s = \tt{0000}$$$. "2 $$$1$$$" — $$$s = \tt{0000}$$$, there are no indices with $$$s_i = \tt{1}$$$, so since the $$$\operatorname{XOR}$$$ of an empty set of numbers is considered to be equal to $$$0$$$, the answer to this query is $$$0$$$.$$$^{\dagger}$$$ A binary string is a string containing only characters $$$\texttt{0}$$$ or $$$\texttt{1}$$$.

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the test.The descriptions of the test cases follow.The first line of each test case description contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the array.The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).The third line of the test case contains the binary string $$$s$$$ of length $$$n$$$.The fourth line of the test case contains one integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of queries.The subsequent $$$q$$$ lines of the test case describe the queries. The first number of each query, $$$tp \in \{1, 2\}$$$, characterizes the type of the query: if $$$tp = 1$$$, then $$$2$$$ integers $$$1 \le l \le r \le n$$$ follow, meaning that the operation of type $$$1$$$ should be performed with parameters $$$l, r$$$, and if $$$tp = 2$$$, then one integer $$$g \in \{0, 1\}$$$ follows, meaning that the operation of type $$$2$$$ should be performed with parameter $$$g$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$, and also that the sum of $$$q$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, and for each query of type $$$2$$$ in it, output the answer to the corresponding query.

Note: Let's analyze the first test case: "2 $$$0$$$" — we are interested in the indices $$$i$$$ for which $$$s_i = \tt{0}$$$, since $$$s = \tt{01000}$$$, these are the indices $$$1, 3, 4$$$, and $$$5$$$, so the answer to the query will be $$$a_1 \oplus a_3 \oplus a_4 \oplus a_5 = 1 \oplus 3 \oplus 4 \oplus 5 = 3$$$. "2 $$$1$$$" — we are interested in the indices $$$i$$$ for which $$$s_i = \tt{1}$$$, since $$$s = \tt{01000}$$$, the only suitable index is $$$2$$$, so the answer to the query will be $$$a_2 = 2$$$. "1 $$$2$$$ $$$4$$$" — we need to replace the characters $$$s_2, s_3, s_4$$$ with their opposites, so before the query $$$s = \tt{01000}$$$, and after the query: $$$s = \tt{00110}$$$. "2 $$$0$$$" — we are interested in the indices $$$i$$$ for which $$$s_i = \tt{0}$$$, since $$$s = \tt{00110}$$$, these are the indices $$$1, 2$$$, and $$$5$$$, so the answer to the query will be $$$a_1 \oplus a_2 \oplus a_5 = 1 \oplus 2 \oplus 5 = 6$$$. "2 $$$1$$$" — we are interested in the indices $$$i$$$ for which $$$s_i = \tt{1}$$$, since $$$s = \tt{00110}$$$, these are the indices $$$3$$$ and $$$4$$$, so the answer to the query will be $$$a_3 \oplus a_4 = 3 \oplus 4 = 7$$$. "1 $$$1$$$ $$$3$$$" — $$$s = \tt{00110}$$$ $$$\to$$$ $$$s = \tt{11010}$$$. "2 $$$1$$$" — we are interested in the indices $$$i$$$ for which $$$s_i = \tt{1}$$$, since $$$s = \tt{11010}$$$, these are the indices $$$1, 2$$$, and $$$4$$$, so the answer to the query will be $$$a_1 \oplus a_2 \oplus a_4 = 1 \oplus 2 \oplus 4 = 7$$$.

Sample Inputs:
5
5
1 2 3 4 5
01000
7
2 0
2 1
1 2 4
2 0
2 1
1 1 3
2 1
6
12 12 14 14 5 5
001001
3
2 1
1 2 4
2 1
4
7 7 7 777
1111
3
2 0
1 2 3
2 0
2
1000000000 996179179
11
1
2 1
5
1 42 20 47 7
00011
5
1 3 4
1 1 1
1 3 4
1 2 4
2 0

Sample Outputs:
3 2 6 7 7 
11 7 
0 0 
16430827 
47

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, arr, s, q) = (readInt(), readList(), readStr(), readInt())
    ps = [0]
    zero = one = 0
    for i in range(n):
        if s[i] == '0':
            zero ^= arr[i]
        else:
            one ^= arr[i]
        ps.append(ps[-1] ^ arr[i])
    ans = []
    for i in range(q):
        arr = readList()
        if arr[0] == 1:
            (_, l, r) = arr
            zero ^= ps[r] ^ ps[l - 1]
            one ^= ps[r] ^ ps[l - 1]
        else:
            ans.append(zero) if arr[1] == 0 else ans.append(one)
    return ans
for _ in range(int(input())):
    print(*solve())

Solution (Python):
import sys
import math
import functools as ft
sys.setrecursionlimit(100000)

def my_input():
    return sys.stdin.readline().strip()

def solve():
    n = int(my_input())
    a = list(map(int, my_input().split()))
    s = my_input()
    allXOR = ft.reduce(lambda x, y: x ^ y, a)
    xr = 0
    pref = [0]
    for i in range(n):
        pref.append(pref[-1] ^ a[i])
        if s[i] == '1':
            xr ^= a[i]
    q = int(my_input())
    ans = []
    for _ in range(q):
        request = list(map(int, my_input().split()))
        if request[0] == 2:
            ans.append(xr if request[1] == 1 else allXOR ^ xr)
        else:
            xr ^= pref[request[2]] ^ pref[request[1] - 1]
    return ' '.join(map(str, ans))

def main():
    print('\n'.join([str(solve()) for _ in range(int(my_input()))]))
main()

Solution (Python):
from sys import stdin, stdout, setrecursionlimit
setrecursionlimit(10 ** 6)
import threading
input = stdin.readline

def ii():
    return int(input())

def lii():
    return list(map(int, stdin.readline().split()))

def ss():
    x = stdin.readline()
    if x and x[-1] == '\n':
        return x[:-1]
    return x

def lss():
    return list(map(str, stdin.readline().split()))

def llss():
    return [i for i in ss()]

def mpi():
    return map(int, input().split())

def yes(flag):
    if flag:
        stdout.write('YES\n')
    else:
        stdout.write('NO\n')

def pl(lst):
    stdout.write(' '.join(map(str, lst)) + '\n')

def ps(n):
    stdout.write(str(n) + '\n')
from collections import defaultdict, deque

def main():
    for _ in range(ii()):
        n = ii()
        a = lii()
        s = ss()
        curr = 0
        (zero, one) = (0, 0)
        pref = []
        for (idx, i) in enumerate(a):
            curr = curr ^ i
            pref.append(curr)
            if s[idx] == '1':
                one = one ^ i
        go = lambda x, y: pref[y] if x == 0 else pref[y] ^ pref[x - 1]
        ans = []
        for _ in range(ii()):
            temp = lii()
            if temp[0] == 1:
                (_, x, y) = temp
                x -= 1
                y -= 1
                val = go(x, y)
                one = one ^ val
            elif temp[1] == 0:
                ans.append(curr ^ one)
            else:
                ans.append(one)
        print(*ans)
threading.stack_size(2 * 10 ** 6)
t = threading.Thread(target=main)
t.start()
t.join()
''