백준19239 min-xor

작성일 | In

문제 링크

  • http://icpc.me/19239

시간복잡도

  • $O(N \log N)$

풀이

고인물이라면 문제를 보자마자 오프라인 동적 연결성처럼 세그먼트 트리 위에서 트라이를 들고 다니면서 DFS하는 풀이가 가장 먼저 떠오를 것입니다. 하지만 이 문제는 메모리 제한이 8MB라서 트라이를 만들 수 없습니다.

사실 잘 생각해 보면, 수들을 오름차순으로 정렬했을 때 인접한 수들의 XOR만 봐도 최솟값을 구할 수 있습니다. 상위 비트가 없어지기 위한 조건을 생각해 보면 직관적으로 알 수 있습니다.
따라서 BBST나 스킵 리스트처럼 원소들의 정렬성을 유지하는 자료구조를 사용하면 온라인으로 해결할 수 있습니다. 원소가 삽입/삭제될 때, 그 원소 근방에서의 XOR값의 변화를 우선 순위 큐 2개 또는 BBST로 관리하면 최솟값을 구할 수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

template<class T=int, class O=less<T>>
struct pq_set {
    priority_queue<T, vector<T>, O> q, del;
    const T& top() const { return q.top(); }
    int size() const { return int(q.size()-del.size()); }
    bool empty() const { return !size(); }
    void insert(const T x) { q.push(x); flush(); }
    void pop() { q.pop(); flush(); }
    void erase(const T x) { del.push(x); flush(); }
    void flush() { while(del.size() && q.top()==del.top()) q.pop(), del.pop(); }
};

int N;
pq_set<int, greater<>> Q;
set<int> S;

void Ins(int v){
    auto it = S.lower_bound(v);
    if(it != S.begin() && it != S.end()) Q.erase(*prev(it) ^ *it);
    it = S.insert(v).first;
    if(it != S.begin()) Q.insert(*prev(it) ^ *it);
    if(next(it) != S.end()) Q.insert(*it ^ *next(it));
}

void Del(int v){
    auto it = S.find(v);
    if(it != S.begin()) Q.erase(*prev(it) ^ *it);
    if(next(it) != S.end()) Q.erase(*it ^ *next(it));
    if(it != S.begin() && next(it) != S.end()) Q.insert(*prev(it) ^ *next(it));
    S.erase(it);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++){
        int op, v=0; cin >> op;
        if(op == 1) cin >> v, Ins(v);
        if(op == 2) cin >> v, Del(v);
        if(op == 3) cout << Q.top() << "\n";
    }
}