Explanation

We can store two variables: one for the XOR of the numbers in group 0 and another for those in group 1. Let's call these $G_0$ and $G_1$ for brevity. This means for queries of type 2, we output either $G_0$ or $G_1$ depending on the parameter.

Type 1 Queries

Let's only consider $G_0$ for now. Say we had to flip $s_i$ when it was initially $1$, so we have to "remove" $a_i$ from $G_0$. Notice that since XORing is its own inverse ($x \oplus x = 0$), we can remove $a_i$ from $G_0$ by setting $G_0$ to $G_0 \oplus a_i$.

On the other hand, if $s_i$ was a $0$ it would become a $1$, and we need to add $a_i$ to $G_0$. Fascinatingly, setting $G_0$ to $G_0 \oplus a_i$ does just what we want as well, since $x \oplus 0 = x$!

The logic for $G_1$ goes much the same way, and so the two values are updated the same way: $G_0 := G_0 \oplus a_i$ and $G_1 := G_1 \oplus a_i$.

Efficient Updates

To update $G_0$ and $G_1$, for a given $l$ and $r$, we must find the XOR of all $a_i$ that are contained in the range.

This can be done in $\mathcal{O}(1)$ time by using prefix sums (or prefix XORs in this case).

Implementation

Time Complexity: $\mathcal{O}(n + q)$

Copy
#include <bits/stdc++.h>
using namespace std;

void solve() {
	int n;
	cin >> n;

	vector<int> a(n);
	for (int i = 0; i < n; i++) { cin >> a[i]; }
	string s;

Copy
import java.io.*;
import java.util.StringTokenizer;

public class DataStructuresFan {
	public static void main(String[] args) throws IOException {
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		int testNum = Integer.parseInt(rd.readLine());
		for (int t = 0; t < testNum; t++) {
			int n = Integer.parseInt(rd.readLine());
			StringTokenizer st = new StringTokenizer(rd.readLine());

Copy
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	g0 = 0
	g1 = 0

	# Construct prefix array
	p = [0] * (n + 1)
	for i in range(1, n + 1):