Fu_L's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Fu-L/cp-library

:heavy_check_mark: verify/unit_test/data_structure/binary_trie.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#include "../../../src/template/template.hpp"
#include "../../../src/data_structure/binary_trie.hpp"
int main() {
    BinaryTrie<int, 3> trie;
    trie.insert(0);
    trie.insert(3);
    trie.insert(7);
    assert(trie.lower_bound(0) == 0);
    assert(trie.lower_bound(8) == 3);
    assert(trie.upper_bound(7) == 3);
    assert(trie.kth_element(1, 1) == 2);
    int a, b;
    cin >> a >> b;
    cout << a + b << '\n';
}
#line 1 "verify/unit_test/data_structure/binary_trie.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
#line 4 "src/template/template.hpp"
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/data_structure/binary_trie.hpp"
template <typename T, int MAX_LOG>
struct BinaryTrie {
    BinaryTrie()
        : root(new Node) {}
    void insert(const T& x) {
        assert(0 <= x and x < (T(1) << MAX_LOG));
        if(!contains(x)) update(x, 1);
    }
    void erase(const T& x) {
        assert(0 <= x and x < (T(1) << MAX_LOG));
        if(contains(x)) update(x, -1);
    }
    bool contains(const T& x) const {
        assert(0 <= x and x < (T(1) << MAX_LOG));
        Node* cur = root;
        for(int i = MAX_LOG - 1; i >= 0; --i) {
            if(!cur) break;
            const int nex = (x >> i) & 1;
            cur = cur->child[nex];
        }
        return cur and cur->cnt;
    }
    int size() const {
        return root->cnt;
    }
    T min(const T& x = 0) const {
        assert(root->cnt > 0);
        assert(0 <= x and x < (T(1) << MAX_LOG));
        return kth_element(0, x);
    }
    T max(const T& x = 0) const {
        assert(root->cnt > 0);
        assert(0 <= x and x < (T(1) << MAX_LOG));
        return kth_element(root->cnt - 1, x);
    }
    T kth_element(int k, const T& x = 0) const {
        assert(0 <= k and k < root->cnt);
        assert(0 <= x and x < (T(1) << MAX_LOG));
        T res = 0;
        Node* cur = root;
        for(int i = MAX_LOG - 1; i >= 0; --i) {
            const int nex = (x >> i) & 1;
            const int cnt = (cur->child[nex] ? cur->child[nex]->cnt : 0);
            if(cnt <= k) {
                k -= cnt;
                res += T(1) << i;
                cur = cur->child[nex ^ 1];
            } else {
                cur = cur->child[nex];
            }
        }
        return res;
    }
    int lower_bound(const T& val, const T& x = 0) const {
        assert(0 <= val and val <= (T(1) << MAX_LOG));
        assert(0 <= x and x < (T(1) << MAX_LOG));
        if(val == (T(1) << MAX_LOG)) return size();
        int res = 0;
        Node* cur = root;
        for(int i = MAX_LOG - 1; i >= 0; --i) {
            if(!cur) break;
            const int xi = (x >> i) & 1, vi = (val >> i) & 1;
            const int nex = xi xor vi;
            if(vi and cur->child[xi]) {
                res += cur->child[xi]->cnt;
            }
            cur = cur->child[nex];
        }
        return res;
    }
    int upper_bound(const T& val, const T& x = 0) const {
        assert(0 <= val and val < (T(1) << MAX_LOG));
        assert(0 <= x and x < (T(1) << MAX_LOG));
        return lower_bound(val + 1, x);
    }

   private:
    struct Node {
        Node* child[2] = {};
        int cnt = 0;
        Node() {}
    };
    Node* root;
    void update(const T& x, const int delta) {
        Node* cur = root;
        cur->cnt += delta;
        for(int i = MAX_LOG - 1; i >= 0; --i) {
            const int nex = (x >> i) & 1;
            if(!cur->child[nex]) {
                cur->child[nex] = new Node;
            }
            cur = cur->child[nex];
            cur->cnt += delta;
        }
    }
};
#line 4 "verify/unit_test/data_structure/binary_trie.test.cpp"
int main() {
    BinaryTrie<int, 3> trie;
    trie.insert(0);
    trie.insert(3);
    trie.insert(7);
    assert(trie.lower_bound(0) == 0);
    assert(trie.lower_bound(8) == 3);
    assert(trie.upper_bound(7) == 3);
    assert(trie.kth_element(1, 1) == 2);
    int a, b;
    cin >> a >> b;
    cout << a + b << '\n';
}
Back to top page