This documentation is automatically generated by online-judge-tools/verification-helper
#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';
}