library
This documentation is automatically generated by online-judge-tools/verification-helper
test/unit/binary_trie.test.cpp
- View this file on GitHub
- Last update: 2026-10-26 02:09:20+09:00
- Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A
Depends on
Code
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <vector>
#include "datastructure/binary_trie.hpp"
template <int log> void run(std::mt19937_64& rng, int iters) {
const long long lim = 1LL << log;
for (int it = 0; it < iters; it++) {
binary_trie<log> t;
std::vector<long long> ms; // multiset
int range = log <= 4 ? int(lim) : 50;
for (int q = 0; q < 200; q++) {
long long x = log <= 4 ? (long long)(rng() % lim) : (rng() % 3 ? (long long)(rng() % range) : (long long)(rng() % lim));
int op = rng() % 4;
if (op == 0) {
int k = rng() % 3;
t.insert(x, k);
for (int i = 0; i < k; i++) ms.push_back(x);
} else if (op == 1) {
int c = int(std::count(ms.begin(), ms.end(), x));
assert(t.count(x) == c);
if (c > 0) {
int k = rng() % (c + 1);
t.erase(x, k);
for (int i = 0; i < k; i++) ms.erase(std::find(ms.begin(), ms.end(), x));
}
}
assert(t.size() == int(ms.size()));
long long v = log <= 4 ? (long long)(rng() % lim) : (rng() % 2 ? (long long)(rng() % range) : (long long)(rng() % lim));
std::vector<long long> xs;
for (long long a : ms) xs.push_back(a ^ v);
std::sort(xs.begin(), xs.end());
long long upper = log <= 4 ? (long long)(rng() % (lim + 2)) - 1 : (long long)(rng() % (range + 2)) - 1;
assert(t.count_less(upper, v) == int(std::lower_bound(xs.begin(), xs.end(), upper) - xs.begin()));
assert(t.count_less(lim, v) == int(xs.size()));
assert(t.count_less(lim + 5, v) == int(xs.size()));
assert(t.count_less(0, v) == 0);
if (!xs.empty()) {
int k = rng() % xs.size();
assert(t.kth_smallest(k, v) == xs[k]);
assert(t.kth_largest(k, v) == xs[xs.size() - 1 - k]);
assert(t.min(v) == xs.front());
assert(t.max(v) == xs.back());
assert(t.min() == *std::min_element(ms.begin(), ms.end()));
}
}
}
}
int main() {
std::mt19937_64 rng(31);
run<3>(rng, 200);
run<30>(rng, 100);
run<62>(rng, 30);
std::cout << "Hello World" << std::endl;
return 0;
}#line 1 "test/unit/binary_trie.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <vector>
#line 2 "datastructure/binary_trie.hpp"
#include <array>
#line 5 "datastructure/binary_trie.hpp"
template <int log = 30> struct binary_trie {
static_assert(1 <= log && log <= 62);
public:
binary_trie() : ch(1, {-1, -1}), cnt(1, 0) {
}
int size() const {
return cnt[0];
}
void insert(long long x, int k = 1) {
assert(0 <= x && x < (1LL << log));
assert(k >= 0);
int v = 0;
cnt[v] += k;
for (int d = log - 1; d >= 0; d--) {
int b = x >> d & 1;
if (ch[v][b] == -1) {
ch[v][b] = int(ch.size());
ch.push_back({-1, -1});
cnt.push_back(0);
}
v = ch[v][b];
cnt[v] += k;
}
}
void erase(long long x, int k = 1) {
assert(0 <= x && x < (1LL << log));
assert(0 <= k && k <= count(x));
int v = 0;
cnt[v] -= k;
for (int d = log - 1; d >= 0; d--) {
v = ch[v][x >> d & 1];
cnt[v] -= k;
}
}
int count(long long x) const {
assert(0 <= x && x < (1LL << log));
int v = 0;
for (int d = log - 1; d >= 0; d--) {
v = ch[v][x >> d & 1];
if (v == -1) return 0;
}
return cnt[v];
}
// #{ a : (a ^ xor_val) < upper }
int count_less(long long upper, long long xor_val = 0) const {
assert(0 <= xor_val && xor_val < (1LL << log));
if (upper <= 0) return 0;
if (upper >= (1LL << log)) return size();
int v = 0, res = 0;
for (int d = log - 1; d >= 0; d--) {
int b = (upper >> d & 1), f = (xor_val >> d & 1);
if (b) {
int c = ch[v][f];
if (c != -1) res += cnt[c];
}
v = ch[v][b ^ f];
if (v == -1) break;
}
return res;
}
// k-th smallest (0-indexed) of { a ^ xor_val }
long long kth_smallest(int k, long long xor_val = 0) const {
assert(0 <= k && k < size());
assert(0 <= xor_val && xor_val < (1LL << log));
int v = 0;
long long res = 0;
for (int d = log - 1; d >= 0; d--) {
int f = xor_val >> d & 1;
int c = ch[v][f];
int c_cnt = c == -1 ? 0 : cnt[c];
if (k < c_cnt) {
v = c;
} else {
k -= c_cnt;
v = ch[v][f ^ 1];
res |= 1LL << d;
}
}
return res;
}
long long kth_largest(int k, long long xor_val = 0) const {
assert(0 <= k && k < size());
return kth_smallest(size() - 1 - k, xor_val);
}
long long min(long long xor_val = 0) const {
return kth_smallest(0, xor_val);
}
long long max(long long xor_val = 0) const {
return kth_smallest(size() - 1, xor_val);
}
private:
std::vector<std::array<int, 2>> ch;
std::vector<int> cnt;
};
#line 9 "test/unit/binary_trie.test.cpp"
template <int log> void run(std::mt19937_64& rng, int iters) {
const long long lim = 1LL << log;
for (int it = 0; it < iters; it++) {
binary_trie<log> t;
std::vector<long long> ms; // multiset
int range = log <= 4 ? int(lim) : 50;
for (int q = 0; q < 200; q++) {
long long x = log <= 4 ? (long long)(rng() % lim) : (rng() % 3 ? (long long)(rng() % range) : (long long)(rng() % lim));
int op = rng() % 4;
if (op == 0) {
int k = rng() % 3;
t.insert(x, k);
for (int i = 0; i < k; i++) ms.push_back(x);
} else if (op == 1) {
int c = int(std::count(ms.begin(), ms.end(), x));
assert(t.count(x) == c);
if (c > 0) {
int k = rng() % (c + 1);
t.erase(x, k);
for (int i = 0; i < k; i++) ms.erase(std::find(ms.begin(), ms.end(), x));
}
}
assert(t.size() == int(ms.size()));
long long v = log <= 4 ? (long long)(rng() % lim) : (rng() % 2 ? (long long)(rng() % range) : (long long)(rng() % lim));
std::vector<long long> xs;
for (long long a : ms) xs.push_back(a ^ v);
std::sort(xs.begin(), xs.end());
long long upper = log <= 4 ? (long long)(rng() % (lim + 2)) - 1 : (long long)(rng() % (range + 2)) - 1;
assert(t.count_less(upper, v) == int(std::lower_bound(xs.begin(), xs.end(), upper) - xs.begin()));
assert(t.count_less(lim, v) == int(xs.size()));
assert(t.count_less(lim + 5, v) == int(xs.size()));
assert(t.count_less(0, v) == 0);
if (!xs.empty()) {
int k = rng() % xs.size();
assert(t.kth_smallest(k, v) == xs[k]);
assert(t.kth_largest(k, v) == xs[xs.size() - 1 - k]);
assert(t.min(v) == xs.front());
assert(t.max(v) == xs.back());
assert(t.min() == *std::min_element(ms.begin(), ms.end()));
}
}
}
}
int main() {
std::mt19937_64 rng(31);
run<3>(rng, 200);
run<30>(rng, 100);
run<62>(rng, 30);
std::cout << "Hello World" << std::endl;
return 0;
}