Data Structures Fan

Explicación

Podemos guardar dos variables: una para el XOR de los números del grupo 0 y otra para los del grupo 1. Las llamamos $G_0$ y $G_1$ por brevedad. Así, en las consultas de tipo 2, imprimimos $G_0$ o $G_1$ según el parámetro.

Consultas de tipo 1

Por ahora consideremos solo $G_0$ . Supongamos que hay que invertir $s_i$ cuando inicialmente era $1$ , de modo que hay que “sacar” $a_i$ de $G_0$ . Nótese que, como el XOR es su propia inversa ( $x \oplus x = 0$ ), podemos sacar $a_i$ de $G_0$ haciendo $G_0 := G_0 \oplus a_i$ .

Por otro lado, si $s_i$ era $0$ pasaría a ser $1$ , y hay que agregar $a_i$ a $G_0$ . Curiosamente, hacer $G_0 := G_0 \oplus a_i$ también logra exactamente eso, porque $x \oplus 0 = x$ .

La lógica para $G_1$ es análoga, así que los dos valores se actualizan de la misma forma: $G_0 := G_0 \oplus a_i$ y $G_1 := G_1 \oplus a_i$ .

Actualizaciones eficientes

Para actualizar $G_0$ y $G_1$ , dados $l$ y $r$ , hay que hallar el XOR de todos los $a_i$ contenidos en el rango.

Esto se puede hacer en $\mathcal{O}(1)$ usando sumas de prefijos (o XOR de prefijos en este caso).

Implementación

Complejidad temporal: $\mathcal{O}(n + q)$

C++JavaPython


#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;
	cin >> s;
 
	int g0 = 0;
	int g1 = 0;
	// Construimos el arreglo de prefijos
	vector<int> p(n + 1);
	for (int i = 1; i <= n; i++) {
		p[i] = p[i - 1] ^ a[i - 1];
		if (s[i - 1] == '1') {
			g1 ^= a[i - 1];
		} else if (s[i - 1] == '0') {
			g0 ^= a[i - 1];
		}
	}
 
	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		int type;
		cin >> type;
		if (type == 1) {
			// Consultas de tipo 1: actualizar g0 y g1
			int l, r;
			cin >> l >> r;
			g0 = g0 ^ (p[r] ^ p[l - 1]);
			g1 = g1 ^ (p[r] ^ p[l - 1]);
		} else {
			// Consultas de tipo 2: imprimir g0 o g1
			int num;
			cin >> num;
			cout << (num == 0 ? g0 : g1) << ' ';
		}
	}
	cout << '\n';
}
 
int main() {
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) { solve(); }
}


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());
			int[] a = new int[n];
			for (int i = 0; i < n; i++) { a[i] = Integer.parseInt(st.nextToken()); }
 
			String s = rd.readLine();
 
			int g0 = 0;
			int g1 = 0;
			// Construimos el arreglo de prefijos
			int[] p = new int[n + 1];
			for (int i = 1; i <= n; i++) {
				p[i] = p[i - 1] ^ a[i - 1];
				if (s.charAt(i - 1) == '1') {
					g1 ^= a[i - 1];
				} else {
					g0 ^= a[i - 1];
				}
			}
 
			int queryNum = Integer.parseInt(rd.readLine());
			for (int q = 0; q < queryNum; q++) {
				st = new StringTokenizer(rd.readLine());
				int type = Integer.parseInt(st.nextToken());
				if (type == 1) {
					// Consultas de tipo 1: actualizar g0 y g1
					int l = Integer.parseInt(st.nextToken());
					int r = Integer.parseInt(st.nextToken());
					g0 ^= p[r] ^ p[l - 1];
					g1 ^= p[r] ^ p[l - 1];
				} else {
					// Consultas de tipo 2: imprimir g0 o g1
					int num = Integer.parseInt(st.nextToken());
					int output = num == 0 ? g0 : g1;
					System.out.print(output + " ");
				}
			}
			System.out.println();
		}
	}
}


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	g0 = 0
	g1 = 0
 
	# Construimos el arreglo de prefijos
	p = [0] * (n + 1)
	for i in range(1, n + 1):
		p[i] = p[i - 1] ^ a[i - 1]
		if s[i - 1] == "1":
			g1 ^= a[i - 1]
		elif s[i - 1] == "0":
			g0 ^= a[i - 1]
 
	for _ in range(int(input())):
		query = list(map(int, input().split()))
		if query[0] == 1:
			# Consultas de tipo 1: actualizar g0 y g1
			l = query[1]
			r = query[2]
			g0 ^= p[r] ^ p[l - 1]
			g1 ^= p[r] ^ p[l - 1]
		elif query[0] == 2:
			# Consultas de tipo 2: imprimir g0 o g1
			print(g0 if query[1] == 0 else g1, end=" ")
 
	print()