0이랑 1만 있는 트라이를 만든다. 입력받는 정수의 맨 앞쪽 비트 (2^29)부터 쭉 훑으면서 둘 다 있으면 XOR값을 최대로 할 수 있도록 선택, 둘 중 하나만 있으면 그거 선택. 다 더하면 정답!
삭제 연산은 cnt를 감소시킨다. cnt가 0이면 그냥 없는거임.
#include <bits/stdc++.h>
using namespace std;
struct Trie {
Trie* child[2];
bool end;
int cnt;
Trie() {
memset(child, 0, sizeof(child));
end = false;
cnt = 1;
}
~Trie() {
for (int i = 0; i < 2; i++) {
if (child[i]) delete child[i];
}
}
void insert(int x, int idx) {
if (idx < 0) {
end = true;
return;
}
bool next = x&(1<<idx);
if (!child[next]) child[next] = new Trie();
else child[next]->cnt++;
child[next]->insert(x, idx-1);
}
void remove(int x, int idx) {
cnt--;
if (idx < 0) return;
bool next = x&(1<<idx);
child[next]->remove(x, idx-1);
}
};
int solve(Trie* node, int x, int idx) {
if (idx < 0) return 0;
bool next = x&(1<<idx);
if (node->child[0] && node->child[0]->cnt && node->child[1] && node->child[1]->cnt) return solve(node->child[!next], x, idx-1) + (1<<idx);
else return node->child[0] && node->child[0]->cnt ? solve(node->child[0], x, idx-1) + (x&(1<<idx))^0 : solve(node->child[1], x, idx-1) + (x&(1<<idx))^(1<<idx);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
Trie root;
root.insert(0, 29);
int m;
cin >> m;
while (m--) {
int q, x;
cin >> q >> x;
if (q == 1) root.insert(x, 29);
else if (q == 2) root.remove(x, 29);
else if (q == 3) cout << solve(&root, x, 29) << '\n';
}
return 0;
}
맨 처음에 숫자 0이 하나 들어가 있으니 주의.
cnt가 0이 되면 메모리 해제하면서 멋있게 짜고싶었는데 실패했다. 나중에 재도전 해봐야겠다.