[Algorithm] cpp 백준 16903번: 수열과 쿼리 20

[Algorithm] cpp 백준 16903번: 수열과 쿼리 20 - XOR 트라이

배열 A(초기에 0 포함)에 대해 삽입·삭제·최대 XOR 질의를 처리합니다. 비트 기반 이진 트라이에 카운트를 유지해 중복과 삭제를 안전히 지원하고, 쿼리 시 각 비트에서 상반된 가지를 우선 선택해 최댓값을 구성합니다. 각 연산은 O(30)로 1초, 512MB 제한에 안전합니다.

문제

링크: https://www.acmicpc.net/problem/16903
요약: 배열 A(초기에 0 포함)에 대해 다음 연산을 처리합니다.
- 1 x: A에 x 추가
- 2 x: A에서 x 1개 제거(항상 존재 보장)
- 3 x: A의 모든 원소와 x의 XOR 중 최댓값 출력
제한: M ≤ 200,000, x ≤ 10^9, 1초, 512MB, 3번 쿼리는 최소 1개 존재

입력/출력

예제 입력 1

예제 출력 1

접근 개요

핵심: 비트 길이 30(0..29) 기준의 이진 트라이를 구성해 각 노드에 “해당 서브트리에 포함된 원소 수(cnt)“를 저장합니다.
삽입/삭제: 경로를 따라 cnt를 ±1로 갱신하여 중복과 삭제를 안정적으로 지원합니다.
질의(최대 XOR): 상위 비트부터 현재 비트의 반대 가지가 존재하고 cnt>0이면 그쪽을, 아니면 같은 비트를 따라 내려가며 결과 비트를 세웁니다.
초기값: A에 0이 존재하므로 시작 시 0을 한 번 삽입해 빈 트라이에서의 질의도 안전하게 합니다.

알고리즘 설계

비트 범위: x ≤ 1e9 < 2^30 이므로 최상위 비트는 29.
연산 정의
- Insert(x): 루트부터 29..0 비트를 따라 자식 노드 없으면 생성, 매 노드 cnt++.
- Erase(x): 동일 경로로 매 노드 cnt–. (입력이 유효하므로 음수 불가)
- Query(x): 각 비트에서 반대 비트 자식의 cnt>0이면 해당 비트에 1을 더하고 그 자식으로 이동, 아니면 같은 비트로 이동.
올바름 근거: XOR을 최대로 하려면 상위 비트부터 가능한 한 서로 다른 비트를 맞추는 탐욕이 전역 최적. cnt로 공집합 경로를 배제해 일관성을 유지합니다.

복잡도

시간: 각 연산 O(30) ≈ O(1) 상수배.
공간: 최대 노드 수 O(30 · 삽입된 고유 값 수) ≤ O(30·M).

구현 (C++)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

struct TrieNode {
	int child[2];
	int cnt;
	TrieNode() : child{-1, -1}, cnt(0) {}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int M;
	if (!(cin >> M)) return 0;

	const int MAX_BIT = 29; // since x ≤ 1e9 < 2^30
	vector<TrieNode> trie;
	trie.reserve(31 * (M + 2));
	trie.emplace_back(); // root

	auto insert_number = [&](int x) {
		int cur = 0;
		trie[cur].cnt++;
		for (int b = MAX_BIT; b >= 0; --b) {
			int bit = (x >> b) & 1;
			if (trie[cur].child[bit] == -1) {
				trie[cur].child[bit] = (int)trie.size();
				trie.emplace_back();
			}
			cur = trie[cur].child[bit];
			trie[cur].cnt++;
		}
	};

	auto erase_number = [&](int x) {
		int cur = 0;
		trie[cur].cnt--;
		for (int b = MAX_BIT; b >= 0; --b) {
			int bit = (x >> b) & 1;
			cur = trie[cur].child[bit];
			trie[cur].cnt--;
		}
	};

	auto query_max_xor = [&](int x) -> int {
		int cur = 0, ans = 0;
		for (int b = MAX_BIT; b >= 0; --b) {
			int bit = (x >> b) & 1;
			int want = bit ^ 1;
			int nxt = trie[cur].child[want];
			if (nxt != -1 && trie[nxt].cnt > 0) {
				ans |= (1 << b);
				cur = nxt;
			} else {
				cur = trie[cur].child[bit];
			}
		}
		return ans;
	};

	// Initial array contains 0
	insert_number(0);

	for (int i = 0; i < M; ++i) {
		int t, x;
		cin >> t >> x;
		if (t == 1) insert_number(x);
		else if (t == 2) erase_number(x);
		else cout << query_max_xor(x) << '\n';
	}
	return 0;
}