DataStructure/test/binary_trie.test.cpp

View this file on GitHub
Last update: 2022-12-29 19:07:59+08:00
Problem: https://judge.yosupo.jp/problem/set_xor_min

Depends on

Code

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

#include "../../template.h"
#include "../BinaryTrie.h"

void solve() {
    BinaryTrie<int, int, 30> trie;
    int q; cin >> q;
    while (q--) {
        int typ, x; cin >> typ >> x;
        if (typ == 0) {
            int has = trie.count(x);
            if (has == 0) trie.insert(x);
        } else if (typ == 1) {
            int has = trie.count(x);
            if (has == 1) trie.remove(x);
        }
        else cout << trie.min_element(x).first << '\n';
    }
}

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

#line 1 "template.h"
#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)

#define DEBUG(x) { cout << #x << " = "; cout << (x) << endl; }
#define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
#define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; }

#define sqr(x) ((x) * (x))

// For printing pair, container, etc.
// Copied from https://quangloc99.github.io/2021/07/30/my-CP-debugging-template.html
template<class U, class V> ostream& operator << (ostream& out, const pair<U, V>& p) {
    return out << '(' << p.first << ", " << p.second << ')';
}

template<class Con, class = decltype(begin(declval<Con>()))>
typename enable_if<!is_same<Con, string>::value, ostream&>::type
operator << (ostream& out, const Con& con) {
    out << '{';
    for (auto beg = con.begin(), it = beg; it != con.end(); it++) {
        out << (it == beg ? "" : ", ") << *it;
    }
    return out << '}';
}
template<size_t i, class T> ostream& print_tuple_utils(ostream& out, const T& tup) {
    if constexpr(i == tuple_size<T>::value) return out << ")"; 
    else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); 
}
template<class ...U> ostream& operator << (ostream& out, const tuple<U...>& t) {
    return print_tuple_utils<0, tuple<U...>>(out, t);
}

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long get_rand(long long r) {
    return uniform_int_distribution<long long> (0, r-1)(rng);
}

template<typename T>
vector<T> read_vector(int n) {
    vector<T> res(n);
    for (int& x : res) cin >> x;
    return res;
}

void solve();

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    solve();
    return 0;
}
#line 1 "DataStructure/BinaryTrie.h"
// Binary Trie
// Based on https://judge.yosupo.jp/submission/72657
// Supports:
// - get min / max / kth element
// - given K, find x: x^K is min / max / kth
//
// Notes:
// - high mem usage. If just need kth_element
//   -> use OrderedSet.h if MAX_VALUE is ~10^6
//   -> use STL/order_statistic.cpp if MAX_VALUE is big / custom type
//
// Tested:
// - (insert, remove, min xor) https://judge.yosupo.jp/problem/set_xor_min
// - (insert, max xor) https://cses.fi/problemset/task/1655/
// Binary trie {{{
template<
    class Val = long long,   // values stored in Trie
    class Count = long long, // frequency of values
    int B = (sizeof(Val) * 8 - 1)  // max number of bit
> struct BinaryTrie {
    struct Node {
        std::array<int, 2> child;
        Count count;
        Node() : child{-1, -1}, count(0) {}
    };

    BinaryTrie() : nodes{Node()} {} // create root node

    // Number of elements in the trie
    Count size() {
        return nodes[0].count;
    }

    void insert(Val x, Count cnt = 1) {
        update(x, cnt);
    }
    void remove(Val x, Count cnt = 1) {
        update(x, -cnt);
    }

    // return min(X ^ xor_val)
    pair<Val, Node> min_element(Val xor_val = 0) {
        assert(0 < size());
        return kth_element(0, xor_val);
    }

    // return max(X ^ xor_val)
    // Tested: https://www.spoj.com/problems/XORX/
    pair<Val, Node> max_element(Val xor_val = 0) {
        assert(0 < size());
        return kth_element(size() - 1, xor_val);
    }

    // return k-th smallest (X ^ xor_val)  (0 <= K < size())
    pair<Val, Node> kth_element(Count k, Val xor_val = 0) {
        assert(0 <= k && k < size());
        int u = 0;
        Val x = 0;
        for (int i = B - 1; i >= 0; i--) {
            int b = get_bit(xor_val, i);
            int v0 = get_child(u, b);
            if (nodes[v0].count <= k) {
                k -= nodes[v0].count;
                u = get_child(u, 1-b);
                x |= 1LL << i;
            } else {
                u = v0;
            }
        }
        return {x, nodes[u]};
    }

    // return frequency of x
    Count count(Val x) {
        int u = 0;
        for (int i = B - 1; i >= 0; i--) {
            int b = get_bit(x, i);
            if (nodes[u].child[b] == -1) {
                return 0;
            }
            u = get_child(u, b);
        }
        return nodes[u].count;
    }

    // return how many values a where a ^ xor_val < x
    // Tested: https://www.spoj.com/problems/SUBXOR/
    Count count_less_than(Val x, Val xor_val) {
        Count sum = 0;
        int u = 0;
        for (int i = B - 1; i >= 0; --i) {
            int bx = get_bit(x, i);
            int bxor = get_bit(xor_val, i);
            if (bx == 1) {
                // i = first bit where a^xor_val differ from x
                if (nodes[u].child[bxor] >= 0) {
                    sum += nodes[nodes[u].child[bxor]].count;
                }
            }
            if (nodes[u].child[bx ^ bxor] == -1) {
                return sum;
            }
            u = get_child(u, bx ^ bxor);
        }
        return sum;
    }

// private:
    vector<Node> nodes;

    int get_child(int p, int b) {
        assert(0 <= p && p < (int) nodes.size());
        assert(0 <= b && b < 2);
        if (nodes[p].child[b] == -1) {
            nodes[p].child[b] = nodes.size();
            nodes.push_back(Node{});
        }
        return nodes[p].child[b];
    }

    void update(Val x, Count cnt) {
        int u = 0;
        for (int i = B - 1; i >= 0; i--) {
            nodes[u].count += cnt;
            assert(nodes[u].count >= 0);  // prevent over delete
            int b = get_bit(x, i);
            u = get_child(u, b);
        }
        nodes[u].count += cnt;
        assert(nodes[u].count >= 0);  // prevent over delete
    }

    inline int get_bit(Val v, int bit) {
        return (v >> bit) & 1;
    }
};
// }}}
#line 5 "DataStructure/test/binary_trie.test.cpp"

void solve() {
    BinaryTrie<int, int, 30> trie;
    int q; cin >> q;
    while (q--) {
        int typ, x; cin >> typ >> x;
        if (typ == 0) {
            int has = trie.count(x);
            if (has == 0) trie.insert(x);
        } else if (typ == 1) {
            int has = trie.count(x);
            if (has == 1) trie.remove(x);
        }
        else cout << trie.min_element(x).first << '\n';
    }
}