Skip to Content
CTRL K

Set XOR-Min

Explicación

Podemos construir un trie binario, con nodos que representan los bits más significativos cerca de la raíz hasta los bits menos significativos. Cuando añadimos o quitamos un número del trie, simplemente añadimos o restamos nodos con su representación binaria. Para responder consultas, podemos bajar por el trie y elegir el mismo bit si es posible para minimizar el xor total. Observemos que cuando bajamos por cualquier camino del trie, está garantizado que llegará hasta el fondo, así que no hay que preocuparse por backtracking.

Implementación

Complejidad temporal: O(qlog⁡x)\mathcal{O}(q\log x)

#include <iostream>
#include <set>
using namespace std;
 
struct Trie {
	Trie *children[2] = {};
	int cnt = 0;  // # of numbers with this bit
};
 
void add(Trie *root, int x) {
	Trie *cur = root;
	for (int i = 30; i >= 0; i--) {
		bool has_bit = x & (1 << i);
		if (cur->children[has_bit] == NULL) {
			// add bit node to trie if there isn't already
			cur->children[has_bit] = new Trie;
		}
		cur->children[has_bit]->cnt++;
		cur = cur->children[has_bit];
	}
}
 
void remove(Trie *root, int x) {
	Trie *cur = root;
	for (int i = 30; i >= 0; i--) {
		bool has_bit = x & (1 << i);
		cur->children[has_bit]->cnt--;
		cur = cur->children[has_bit];
	}
}
 
int query(Trie *root, int x) {
	Trie *cur = root;
	int res = 0;
	for (int i = 30; i >= 0; i--) {
		bool has_bit = x & (1 << i);
		if (cur->children[has_bit] != NULL && cur->children[has_bit]->cnt > 0) {
			// we go down the same bit
			cur = cur->children[has_bit];
		} else {
			/*
			 * we go down a different bit,
			 * xor increases by 2^i
			 */
			cur = cur->children[!has_bit];
			res += 1 << i;
		}
	}
	return res;
}
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	Trie tr;
	int q;
	cin >> q;
	set<int> s;
	for (int qry = 0; qry < q; qry++) {
		int t, x;
		cin >> t >> x;
		if (t == 0) {
			if (!s.count(x)) {
				s.insert(x);
				add(&tr, x);
			}
		} else if (t == 1) {
			if (s.count(x)) {
				s.erase(x);
				remove(&tr, x);
			}
		} else {
			cout << query(&tr, x) << "\n";
		}
	}
}
Fundamentos