Maximum Xor Subarray

Explicación

Sea $\texttt{pref}_i$ la xor-suma del prefijo que termina en $i$ . Debemos hallar una suma de prefijo anterior $\texttt{pref}_j$ tal que $\texttt{pref}_i \oplus \texttt{pref}_j$ se maximice.

Para obtener el resultado máximo, los bits $0$ deberían voltearse a $1$ . Ahora, podemos usar un Trie para mantener las representaciones binarias de las xor-sumas de los prefijos. Añadimos los valores en el Trie del bit más significativo al menos significativo.

Al consultar por $\texttt{pref}_j$ recorremos el Trie intentando bajar por el camino del bit opuesto, de modo que al hacer xor con $\texttt{pref}_i$ se voltean más bits a $1$ .

Implementación

Complejidad temporal: $\mathcal{O}(N \cdot \log{M})$ , donde $M$ es el valor máximo

C++


#include <bits/stdc++.h>
using namespace std;
 
const int MAX_N = 2e5;
 
int node_count;
int trie[32 * MAX_N][2];  // 32 bits en un int
 
void insert(int val) {
	int node = 0;
	// Recorremos la representación binaria de val
	for (int i = 31; i >= 0; i--) {
		// Obtenemos el valor del bit actual
		bool bit = val & (1 << i);
		// Si el nodo no existe, creamos uno
		if (trie[node][bit] == 0) { trie[node][bit] = ++node_count; }
		// Pasamos al siguiente nodo
		node = trie[node][bit];
	}
}
 
int query(int xor_sum) {
	int node = 0;
	int path = 0;  // path reconstruye el número en el Trie
 
	// Recorremos la representación binaria de val
	for (int i = 31; i >= 0; i--) {
		// Obtenemos el valor del bit actual
		bool bit = xor_sum & (1 << i);
		// Primero intentamos el valor opuesto del bit, para que el xor dé 1
		if (trie[node][1 ^ bit]) {
			if (1 ^ bit) path |= (1 << i);
			node = trie[node][1 ^ bit];
		} else if (trie[node][bit]) {
			if (bit) path |= (1 << i);
			node = trie[node][bit];
		}
	}
 
	// Devolver pref_i ^ pref_j
	return xor_sum ^ path;
}
 
int main() {
	int n;
	cin >> n;
 
	insert(0);
 
	int xor_sum = 0;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
 
		// Insertamos la xor-suma de prefijo en el Trie
		xor_sum ^= x;
		insert(xor_sum);
 
		ans = max(ans, query(xor_sum));
	}
 
	cout << ans << endl;
}