Xor-MST

Solución

El editorial oficial  usa una solución con el algoritmo de Boruvka. Hay una solución más simple usando divide y vencerás.

Primero, nótese que como esencialmente hay una arista entre cualquier par de nodos, los valores de los nodos mismos se pueden considerar no ordenados. Así, la respuesta no cambiará si ordenamos los elementos.

Segundo, nótese que los elementos duplicados se pueden quitar. Esto es porque los elementos duplicados se pueden conectar con una arista de costo 0.

Después de estos dos pasos, obtuvimos un arreglo ordenado sin duplicados cuya respuesta es la misma que la del problema original.

Ahora consideremos algún subarreglo $[l, r]$ así como algún bit $b$ ($0 \leq l \leq r < N$, $0 \leq b < 30$). Partimos el subarreglo en dos conjuntos $L$ y $R$, donde $R$ contiene todos los elementos con el bit $b$ activado, y $L$ contiene los demás elementos. Asumiremos que $b$ es el primer bit distinto; es decir, todos los elementos del subarreglo tienen los mismos bits para todos los bits mayores que $b$.

Como $b$ es el primer bit distinto y como el arreglo está ordenado, $L$ contiene algún prefijo del subarreglo y $R$ contiene algún sufijo. Es decir, $L = A[l:m - 1]$ y $R = [m : r]$ para algún $l < m \leq r$.

Lema: En un árbol de expansión mínima XOR, hay exactamente 1 arista entre un elemento de $L$ y un elemento de $R$.

Demostración: Por definición, un árbol de expansión debe conectar todos los vértices, lo que implica la existencia de al menos 1 arista entre $L$ y $R$. Asumamos que hay dos aristas entre $L$ y $R$, con extremos $(l_1, r_1)$ y $(l_2, r_2)$ respectivamente, donde $l_1, l_2 \in L$ y $r_1, r_2 \in R$. El árbol se construye de una de las siguientes formas, donde las líneas sólidas representan aristas y las punteadas representan caminos.

Sin pérdida de generalidad, desconectemos $(l_2, r_2)$. El árbol de expansión queda desconectado, con $l_2$ o $r_2$ en el componente que no contiene $l_1$ y $r_1$. Siempre es más óptimo conectar este nodo al nodo extremo correspondiente. Es decir, si $l_2$ no está en el mismo componente que $l_1$, entonces una arista entre $l_1$ y $l_2$ siempre será mejor que una entre $l_2$ y $r_2$.

Por definición, $l_1$ y $l_2$ comparten un bit $b$, así que el XOR de sus valores no contiene el bit $b$, mientras que $l_2 \texttt{ xor } r_2$ siempre contiene $b$. Nótese que esto implica que siempre es mejor conectar $l_2$ a $l_1$; sin embargo, esta configuración puede no ser óptima. La demostración es análoga si en cambio se desconecta $r_2$. $\blacksquare$

Así, el algoritmo de divide y vencerás procederá de la siguiente forma: Partiremos el subarreglo en $L$ y $R$. Este paso toma tiempo $\mathcal{O}(n)$. Nótese que si $L$ o $R$ está vacío (si todos los números del rango contienen $b$ o si ninguno de ellos contiene $b$), inmediatamente recurrimos con el mismo subarreglo y $b - 1$ como bit. Luego, elegiremos un elemento de $L$ y un elemento de $R$ con XOR por pares mínimo, y lo sumaremos a la respuesta. Por último, ejecutamos recursivamente el algoritmo sobre $L$ y $R$ con bit $b - 1$.

¿Cómo hallamos dos valores tales que su XOR se minimice? Una forma de hacer esto de forma eficiente es con un trie. En el trie, cada número se representa como un string de su representación binaria, empezando por el dígito más significativo y terminando por el menos. Para consultas XOR, podemos hacer un recorrido voraz de raíz a hoja. Cuando existe una transición que corresponde al bit actual del número de consulta, tomamos esa transición de forma voraz; en caso contrario, nos vemos forzados a tomar la transición no óptima, y sumamos el peso de ese bit a la respuesta.

Implementación

Complejidad temporal: Sea $n$ la longitud del arreglo, y sea $a$ el valor de un elemento arbitrario. Hay $\log a \approx 30$ niveles de recursión, cada uno conteniendo exactamente $n$ elementos. Además, cada inserción/consulta en el trie toma tiempo $\mathcal{O}(\log a)$, ya que hay que recorrer a lo sumo el número de bits distintos de $a$. Combinando esta información, la complejidad temporal total es $\mathcal{O}(n \log^2 a)$.

#include <bits/stdc++.h>
using namespace std;
 
const long long INF = 2000000011;
 
int N;
long long A[200005];
 
namespace Trie {
struct Node {
	int l = -1, r = -1;
};
 
int B;
vector<Node> nodes;
 
int newNode() {
	nodes.emplace_back();
	return nodes.size() - 1;
}
 
void init(int _B) {
	B = _B;
	nodes.clear();
	newNode();
}
 
void insert(int n) {
	int u = 0;
	for (int i = B; i >= 0; i--) {
		if ((n >> i) & 1) {
			if (nodes[u].r == -1) { nodes[u].r = newNode(); }
			u = nodes[u].r;
		} else {
			if (nodes[u].l == -1) { nodes[u].l = newNode(); }
			u = nodes[u].l;
		}
	}
}
 
int query(int n) {
	int u = 0, ans = 0;
	for (int i = B; i >= 0; i--) {
		if ((n >> i) & 1) {
			if (nodes[u].r != -1) {
				u = nodes[u].r;
			} else {
				ans |= (1 << i);
				u = nodes[u].l;
			}
		} else {
			if (nodes[u].l != -1) {
				u = nodes[u].l;
			} else {
				ans |= (1 << i);
				u = nodes[u].r;
			}
		}
	}
	return ans;
}
}  // namespace Trie
 
long long ans = 0;
 
void dnq(int l = 0, int r = N - 1, int b = 29) {
	if (l >= r) { return; }
 
	Trie::init(b);
	int m = 0, tans = INF;
	for (m = l; m <= r && !((A[m] >> b) & 1); m++) { Trie::insert(A[m]); }
	if (m == l || m == r + 1) { return dnq(l, r, b - 1); }
	for (int i = m; i <= r; i++) { tans = min(tans, Trie::query(A[i])); }
	ans += tans == INF ? 0 : tans;
 
	dnq(l, m - 1, b - 1);
	dnq(m, r, b - 1);
}
 
int main() {
	cin >> N;
	{
		set<int> S;
		for (int i = 0; i < N; i++) {
			int a;
			cin >> a;
			S.insert(a);
		}
		for (int i = 0; int s : S) { A[i++] = s; }
		N = S.size();
	}
 
	dnq();
 
	cout << ans << '\n';
}