[BOJ/Platinum 3] 백준 16903 수열과 쿼리 20(C++)

문제 링크

https://www.acmicpc.net/problem/16903

16903번: 수열과 쿼리 20

 

문제

0이 하나 포함되어 있는 배열 A가 있다. 이때, 다음 쿼리를 수행해야 한다.

• 1 x: A에 x를 추가한다.
• 2 x: A에서 x를 제거한다. A에 x가 두 개 이상 있는 경우에는 하나만 삭제한다. 항상 A에 x가 있는 쿼리만 주어진다.
• 3 x: A에 포함된 각각의 원소와 x를 XOR 연산을 한 다음, 가장 큰 값을 출력한다.

입력

첫째 줄에 쿼리의 개수 M(1 ≤ M ≤ 200,000)이 주어진다. 둘째 줄부터 M개의 줄에 쿼리가 주어진다. 입력으로 주어지는 x의 범위는 109보다 작거나 같은 자연수이다.

3번 쿼리는 하나 이상 주어진다.

출력

쿼리를 수행한 결과를 출력한다.

예제 입력 1

10
1 8
1 9
1 11
1 6
1 1
3 3
2 8
3 3
3 8
3 11

예제 출력 1

11
10
14
13

알고리즘 분류

• 트라이

풀이

수열에 정수를 추가할 때 정수를 이진수로 변환하고 트라이에 insert한다.

수열에서 정수를 삭제할 때에는 끝 노드에 기록된 수열에 존재하는 정수의 개수를 1만큼 차감한다. 이 개수가 0이 되었다면 수열에 더 이상 해당 정수가 존재하지 않는다는 뜻이므로, 트라이에서도 해당 정수를 제거한다.

처음에 끝 노드까지 내려간 후, 해당 노드가 더 이상 끝 노드가 아니라고 표시해준 후 노드의 자식 노드가 없을 경우 메모리를 해제해준다.

그리고 다시 Bottom-Up 방식으로 상위 노드들의 자식 노드가 없다면 역시 제거해준다.

이런 식으로 트라이에서 정수를 삭제할 수 있다.

최댓값을 구하기 위해서는 정수 X를 이진수로 변환한 후 높은 자리수부터 순차적으로 현재 노드의 비트를 비교해서 최대한 1을 많이 갖는 값을 찾아야 한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct TRIE {
    bool isEnd;
    int Count;
    LL finish_Number;
    TRIE* Child[2];

    TRIE() {
        isEnd = false;
        Count = 0;
        for (int i = 0; i < 2; i++) {
            Child[i] = nullptr;
        }
    }

    void insert_Pattern(string Pattern, LL Number) {
        TRIE* NowTrie = this;

        for (int i = 0; i < Pattern.size(); i++) {
            int Now = Pattern[i] - '0';

            if (NowTrie->Child[Now] == nullptr) {
                NowTrie->Child[Now] = new TRIE;
            }

            NowTrie = NowTrie->Child[Now];
        }

        NowTrie->isEnd = true;
        NowTrie->finish_Number = Number;
        NowTrie->Count++;
    }

    LL query(string NowS, LL NowN) {
        LL Result = NowN;
        TRIE* NowTrie = this;

        for (int i = 0; i < NowS.size(); i++) {
            int Now = NowS[i] - '0';
            if (NowTrie->Child[Now ^ 1] != nullptr) {
                NowTrie = NowTrie->Child[Now ^ 1];
            }
            else {
                NowTrie = NowTrie->Child[Now];
            }
        }

        Result ^= NowTrie->finish_Number;
        return Result;
    }
};

int M, I;
LL X;
bool isZero;

string make_String(LL Number) {
    string Result = "";
    while (1) {
        if (Number == 0) {
            break;
        }

        Result = to_string(Number % 2) + Result;
        Number /= 2;
    };
    int Sub = 32 - (int)Result.length();
    string tmp = "";
    while (Sub--) {
        tmp += '0';
    };
    Result = tmp + Result;

    return Result;
}

void delete_Pattern(TRIE*& Here, string Pattern, int Index) {
    int Length = (int)Pattern.length();

    if (Index == Length) {
        Here->Count--;
        if (Here->Count == 0) {
            isZero = true;
            Here->isEnd = false;
            bool Flag = true;
            for (int i = 0; i < 2; i++) {
                if (Here->Child[i]) {
                    Flag = false;
                    break;
                }
            }
            if (Flag) {
                Here = nullptr;
            }
        }
    }
    else {
        int Now = Pattern[Index] - '0';
        delete_Pattern(Here->Child[Now], Pattern, Index + 1);
        if (isZero) {
            bool Flag = true;
            for (int i = 0; i < 2; i++) {
                if (Here->Child[i]) {
                    Flag = false;
                    break;
                }
            }
            if (Flag && !Here->isEnd) {
                Here = nullptr;
            }
        }
    }
}

void input() {
    TRIE* Root = new TRIE();
    Root->insert_Pattern(make_String(0), 0);
    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> I >> X;
        string NewX = make_String(X);
        if (I == 1) {
            Root->insert_Pattern(NewX, X);
        }
        else if (I == 2) {
            isZero = false;
            delete_Pattern(Root, NewX, 0);
        }
        else {
            TRIE* NowTrie = Root;
            cout << NowTrie->query(NewX, X) << "\n";
        }
    }
    delete Root;
}

int main() {
    FASTIO
    input();

    return 0;
}