verify/yosupo/yosupo_set_xor_min.test.cpp

View this file on GitHub
Last update: 2025-03-02 08:28:35+09:00
Problem: https://judge.yosupo.jp/problem/set_xor_min

Depends on

data_structure/binary_trie.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/set_xor_min"

#include <bits/stdc++.h>
using namespace std;

#include "../../data_structure/binary_trie.hpp"

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

    BinaryTrie bt;

    while(Q--) {
        int t, x;
        cin >> t >> x;
        if(t == 0) {
            if(!bt.find(x)) bt.insert(x);
        }
        if(t == 1) {
            if(bt.find(x)) bt.erase(x);
        }
        if(t == 2) {
            cout << (bt.xor_min(x) ^ x) << "\n";
        }
    }

    return 0;
}

#line 1 "verify/yosupo/yosupo_set_xor_min.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/set_xor_min"

#include <bits/stdc++.h>
using namespace std;

#line 1 "data_structure/binary_trie.hpp"
template<typename U = unsigned, int B = 32>
struct BinaryTrie {
    struct Node {
        int cnt;
        Node *ch[2];
        Node() : cnt(0), ch{nullptr, nullptr} {}
    };

    BinaryTrie() : root(nullptr) {}

    void insert(U x) { insert(root, x); }
    void erase(U x) { erase(root, x); }
    bool find(U x) { return find(root, x); }
    U xor_max(U x) { return xor_min(root, ~x); }
    U xor_min(U x) { return xor_min(root, x); }

  private: 
    Node* root;

    void insert(Node*& n, U x, int b = B - 1) {
        if(n == nullptr) n = new Node();
        n->cnt++;
        if(b >= 0) insert(n->ch[(x >> b) & 1], x, b - 1);
    }    
    void erase(Node*& n, U x, int b = B - 1) {
        if(b >= 0) erase(n->ch[(x >> b) & 1], x, b - 1);
        if(n && --n->cnt == 0) { delete n; n = nullptr; }
    }
    bool find(Node* n, U x, int b = B - 1) {
        if(n == nullptr) return false;
        if(b < 0) return true;
        if(n->ch[(x >> b) & 1] == nullptr) return false;
        return find(n->ch[(x >> b) & 1], x, b - 1);
    }
    U xor_min(Node* n, U x, int b = B - 1) {
        if(b < 0) return 0;
        bool f = (x >> b) & 1;
        if(n->ch[f] == nullptr) f ^= 1;
        return xor_min(n->ch[f], x, b - 1) | ((U)f << b);
    }
};
#line 7 "verify/yosupo/yosupo_set_xor_min.test.cpp"

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

    BinaryTrie bt;

    while(Q--) {
        int t, x;
        cin >> t >> x;
        if(t == 0) {
            if(!bt.find(x)) bt.insert(x);
        }
        if(t == 1) {
            if(bt.find(x)) bt.erase(x);
        }
        if(t == 2) {
            cout << (bt.xor_min(x) ^ x) << "\n";
        }
    }

    return 0;
}