matsutaku-library
This documentation is automatically generated by competitive-verifier/competitive-verifier
test/standalone/integer_set_test.cpp
- View this file on GitHub
- Last update: 2024-07-11 22:21:57+09:00
Depends on
Code
#define STANDALONE
#include "include/mtl/integer_set.hpp"
#include "set_test.hpp"
constexpr int W = 20;
//constexpr int Max = 4e5;
//
//template<typename Set>
//int test_set() {
// std::vector<int> values;
// while (values.empty()) {
// for (int i = 0; i < Max; i++) {
// if (i == 0 or rand()%4 == 0)
// values.push_back(i);
// }
// }
// int n = values.size();
// std::vector<int> shuffled = values;
// for (int i = 0; i < n; i++) {
// std::swap(shuffled[i], shuffled[rand()%n]);
// }
//
// Set S;
// for (int v : shuffled) {
// S.insert(v);
// }
//// S.print_for_debug();
// int target = -1;
// int pred = -1;
// int succ = values[0];
// int k = 0;
// auto log = [&]() {
// std::cout << pred << ' ' << target << ' ' << succ << std::endl;
// assert(false);
// };
// for (int i = 0; i < Max; i++) {
// if (k < n and values[k] == i) {
// target = values[k];
// pred = k-1 >= 0 ? values[k-1] : -1;
// succ = k+1 < n ? values[k+1] : -1;
// k++;
// } else {
// pred = k-1 >= 0 ? values[k-1] : -1;
// target = -1;
// }
//
// auto fit = S.find(i);
// if (fit != S.end()) {
// if ((int) *fit != i) {
// std::cout << "find: " << i << std::endl;
// log();
// return 1;
// }
// } else {
// if (target != -1) {
// log();
// return 1;
// }
// }
//
// auto sucit = S.successor(i);
// if (sucit != S.end()) {
// if ((int) *sucit != succ) {
// std::cout << "succ: " << *sucit << std::endl;
// log();
// return 1;
// }
// } else {
// if (succ != -1) {
// log();
// return 1;
// }
// }
//
// auto predit = S.predecessor(i);
// if (predit != S.end()) {
// if ((int) *predit != pred) {
// std::cout << "pred: " << *predit << std::endl;
// log();
// return 1;
// }
// } else {
// if (pred != -1) {
// log();
// return 1;
// }
// }
// }
//
// int size = n;
// if ((int) S.size() != size) {
// std::cout << S.size() << ' ' << size<< std::endl;
// log();
// return 1;
// }
// for (int v : shuffled) {
// S.erase(v);
// size--;
// if ((int) S.size() != size) {
// std::cout << S.size() << ' ' << size<< std::endl;
// assert(false);
// return 1;
// }
// }
// return 0;
//}
int main() {
// mtl::integer_set_test<XFastTrieSet<W>>();
// mtl::integer_set_test<YFastTrieSet<W>>();
std::cout << "OK" << std::endl;
}
#line 1 "test/standalone/integer_set_test.cpp"
#define STANDALONE
#line 2 "include/mtl/treap.hpp"
#include <memory>
#include <iterator>
#include <cassert>
#include <exception>
#include <random>
#include <iostream>
template<class T, class V=void,
class Compare = std::less<>,
bool UniqueKey = true>
class Treap {
public:
using key_type = T;
static constexpr bool kKeyOnly = std::is_same<V, void>::value;
using mapped_type = typename std::conditional<kKeyOnly, T, V>::type;
using value_type = typename std::conditional<
kKeyOnly,
T,
std::pair<T const, V>
>::type;
using raw_key_type = typename std::conditional<kKeyOnly, T, typename std::remove_const<T>::type>::type;
using raw_value_type = typename std::conditional<kKeyOnly, T, typename std::remove_const<V>::type>::type;
using init_type = typename std::conditional<
kKeyOnly,
T,
std::pair<raw_key_type, raw_value_type>
>::type;
using priority_type = uint32_t;
protected:
template<bool> struct iterator_base;
public:
using iterator = iterator_base<false>;
using const_iterator = iterator_base<true>;
private:
struct Node;
using node_ptr = std::shared_ptr<Node>;
using node_weak = std::weak_ptr<Node>;
struct Node {
node_ptr left, right;
node_weak parent;
priority_type p;
value_type v;
explicit Node(priority_type p)
: left(nullptr), right(nullptr), p(p) {}
explicit Node(priority_type p, const value_type& v)
: left(nullptr), right(nullptr), p(p), v(v) {}
explicit Node(priority_type p, value_type&& v)
: left(nullptr), right(nullptr), p(p), v(std::forward<value_type>(v)) {}
template<typename... Args>
explicit Node(priority_type p, Args&&... args)
: left(nullptr), right(nullptr), p(p),
v(std::forward<Args>(args)...) {}
const raw_key_type& key() const {
if constexpr (kKeyOnly)
return v;
else
return v.first;
}
};
node_ptr sentinel_;
size_t size_;
std::default_random_engine eng;
std::uniform_int_distribution<priority_type> dist;
Compare comp_;
public:
Treap(const Compare& comp = Compare())
: sentinel_(std::make_shared<Node>(0)), size_(0),
comp_(comp) {}
template<typename It>
explicit Treap(It begin, It end,
const Compare& comp = Compare()) : Treap(comp) {
insert(begin, end);
}
Treap(std::initializer_list<value_type> list) : Treap(list.begin(), list.end()) {}
private:
void _clone(node_ptr u, const node_ptr ru) {
if (ru->left) {
u->left = std::make_shared<Node>(ru->left->p, ru->left->v);
u->left->parent = u;
_clone(u->left, ru->left);
}
if (ru->right) {
u->right = std::make_shared<Node>(ru->right->p, ru->right->v);
u->right->parent = u;
_clone(u->right, ru->right);
}
}
public:
Treap(const Treap& r) : Treap() {
_clone(sentinel_, r.sentinel_);
size_ = r.size_;
}
Treap& operator=(const Treap& r) {
clear();
_clone(sentinel_, r.sentinel_);
size_ = r.size_;
return *this;
}
Treap(Treap&& r) noexcept = default;
Treap& operator=(Treap&& r) noexcept = default;
private:
bool _check_connection(node_ptr u) const {
if (!u)
return false;
assert(u != sentinel_ or sentinel_->right == nullptr);
if (u == sentinel_ and u->right)
return true;
if (u->left) {
assert(u->left->parent == u);
if (!(u->left->parent == u))
return true;
}
if (u->right) {
assert(u->right->parent == u);
if (!(u->right->parent == u))
return true;
}
if (_check_connection(u->left))
return true;
if (_check_connection(u->right))
return true;
return false;
}
node_ptr _root() const {
return sentinel_->left;
}
priority_type _pick_priority() { return dist(eng); }
bool _comp_priority(node_ptr u, node_ptr v) const {
return u->p < v->p;
}
void _turn_left(node_ptr u) {
auto p = u->parent.lock();
auto r = u->right;
assert(p);
assert(r);
if (p->left == u)
p->left = r;
else {
assert(p->right == u);
p->right = r;
}
r->parent = p;
auto rl = r->left;
u->right = rl;
if (rl) rl->parent = u;
r->left = u;
u->parent = r;
}
void _turn_right(node_ptr u) {
auto p = u->parent.lock();
auto l = u->left;
assert(p);
assert(l);
if (p->left == u)
p->left = l;
else {
assert(p->right == u);
p->right = l;
}
l->parent = p;
auto lr = l->right;
u->left = lr;
if (lr) lr->parent = u;
l->right = u;
u->parent = l;
}
template<typename Cond>
void _bubble_up_cond(node_ptr u, Cond cond) {
while (cond(u)) {
assert(!u->parent.expired());
auto p = u->parent.lock();
assert(p != sentinel_);
if (p->right == u) {
_turn_left(p);
} else {
assert(p->left == u);
_turn_right(p);
}
}
}
void _bubble_up(node_ptr u) {
_bubble_up_cond(u, [&](node_ptr u) { return _comp_priority(u, u->parent.lock()); });
}
void _bubble_up_force(node_ptr u) {
_bubble_up_cond(u, [&](node_ptr u) { return u->parent.lock() != sentinel_; });
assert(u->parent.lock() == sentinel_);
assert(_root() == u);
}
void _tricle_down(node_ptr u) {
while (u->left or u->right) {
if (!u->right) {
_turn_right(u);
} else if (!u->left) {
_turn_left(u);
} else if (_comp_priority(u->left, u->right)) {
_turn_right(u);
} else {
_turn_left(u);
}
}
}
// Used for leaf only (done after _tricle_down)
void _splice(node_ptr u) {
assert(!u->left and !u->right);
auto p = u->parent.lock();
assert(p);
if (p->left == u)
p->left = nullptr;
else {
assert(p->right == u);
p->right = nullptr;
}
u->parent.reset();
}
// NOTE: value of size_ is broken.
Treap(node_ptr node) : Treap() {
sentinel_->left = node;
if (node)
node->parent = sentinel_;
}
std::pair<iterator, bool> _insert_node_subtree(node_ptr u, node_ptr new_node) {
auto x = new_node->key();
while (true) {
if constexpr (UniqueKey) if (u != sentinel_ and x == u->key())
return std::make_pair(iterator(u), false);
auto& c = u == sentinel_ or comp_(x, u->key()) ? u->left : u->right;
if (!c) {
c = new_node;
c->parent = u;
u = c;
break;
} else {
u = c;
}
}
_bubble_up(u);
++size_;
return std::make_pair(iterator(u), true);
}
std::pair<iterator, bool> _insert_node(node_ptr new_node) {
return _insert_node_subtree(sentinel_, new_node);
}
iterator _insert_node_hint(const_iterator hint, node_ptr new_node) {
auto x = new_node->key();
auto u = hint.ptr_;
if (!u->parent.expired()) {
auto p = u->parent.lock();
if (p != sentinel_) {
T xp = p->key();
if constexpr (UniqueKey) if (xp == x) [[unlikely]]
return iterator(p);
// Check hint is malicious
if ( (p->left == u and comp_(xp, x))
or (p->right == u and comp_(x, xp))) [[unlikely]]
return _insert_node(new_node).first;
//
}
}
return _insert_node_subtree(u, new_node).first;
}
public:
size_t size() const { return size_; } // TODO: split break size
bool empty() const { return _root() == nullptr; }
void clear() {
sentinel_->left = nullptr;
size_ = 0;
}
iterator find(T x) const {
node_ptr u = _root();
while (u) {
if (u->key() == x)
return iterator(u);
if (comp_(x, u->key()))
u = u->left;
else
u = u->right;
}
return end();
}
size_t count(T x) const { return (size_t) (find(x) != end()); }
iterator lower_bound(T x) const {
node_ptr u = _root();
node_ptr lb = sentinel_;
while (u) {
if (u->key() == x)
return iterator(u);
if (comp_(x, u->key())) {
lb = u;
u = u->left;
} else {
u = u->right;
}
}
return iterator(lb);
}
iterator upper_bound(T x) const {
node_ptr u = _root();
node_ptr ub = sentinel_;
while (u) {
if (comp_(x, u->key())) {
ub = u;
u = u->left;
} else {
u = u->right;
}
}
return iterator(ub);
}
iterator successor(T x) const { return upper_bound(x); }
iterator predecessor(T x) const {
auto u = _root();
node_ptr pr = sentinel_;
while (u) {
if (!comp_(u->key(), x)) {
u = u->left;
} else {
pr = u;
u = u->right;
}
}
return iterator(pr);
}
private:
template<typename... Args>
node_ptr _create_node(Args&&... args) {
auto p = _pick_priority();
return std::make_shared<Node>(p, std::forward<Args>(args)...);
}
public:
template<typename ...Args>
std::pair<iterator, bool> emplace(Args&&... args) {
return _insert_node(_create_node(std::forward<Args>(args)...));
}
template<typename ...Args>
iterator emplace_hint(const_iterator hint, Args&&... args) {
return _insert_node_hint(hint, _create_node(std::forward<Args>(args)...));
}
std::pair<iterator, bool> insert(const init_type& e) {
return emplace(e);
}
std::pair<iterator, bool> insert(init_type&& e) {
return emplace(std::move(e));
}
template<typename=void>
std::pair<iterator, bool> insert(const value_type& e) {
return emplace(e);
}
template<typename=void>
std::pair<iterator, bool> insert(value_type&& e) {
return emplace(std::move(e));
}
template<class It>
void insert(It begin, It end) {
using traits = std::iterator_traits<It>;
static_assert(std::is_convertible<typename traits::value_type, value_type>::value, "");
static_assert(std::is_base_of<std::forward_iterator_tag, typename traits::iterator_category>::value, "");
for (auto it = begin; it != end; ++it)
emplace(*it);
}
void insert(std::initializer_list<value_type> list) {
insert(list.begin(), list.end());
}
iterator erase(iterator it) {
if (it == end())
return end();
auto u = it.ptr_;
auto p = u->parent;
_tricle_down(u);
auto ret = ++iterator(u);
_splice(u);
--size_;
return ret;
}
bool erase(T x) {
auto it = find(x);
if (it != end()) {
erase(it);
return 1;
} else {
return 0;
}
}
iterator erase(iterator begin, iterator end) {
auto _l = split(begin);
auto _m = split(end);
return absorb(&_l);
}
[[nodiscard]] Treap split(iterator it) {
// !!! Breaking size_ value !!!
auto u = it.ptr_;
auto d = std::make_shared<Node>(std::numeric_limits<priority_type>::max());
auto lu = u->left;
d->left = lu;
d->parent = u;
u->left = d;
if (lu) lu->parent = d;
_bubble_up_force(d);
auto l = d->left;
auto r = d->right;
sentinel_->left = r;
if (r) r->parent = sentinel_;
if (l) l->parent.reset();
return Treap(l);
}
iterator absorb(Treap* s) {
assert((s and s->empty()) or empty() or comp_(*--s->end(), *begin()));
auto it = begin();
if (!s or s->empty()) return it;
if (empty()) {
sentinel_->left = s->_root();
sentinel_->left->parent = sentinel_;
size_ = s->size_;
s->clear();
return begin();
}
auto d = std::make_shared<Node>(0);
d->left = s->_root();
d->right = _root();
d->parent = sentinel_;
if (d->left)
d->left->parent = d;
if (d->right)
d->right->parent = d;
sentinel_->left = d;
_tricle_down(d);
_splice(d);
size_ += s->size_;
s->clear();
return it;
}
protected:
template<bool Const>
struct iterator_base {
public:
using difference_type = ptrdiff_t;
using value_type = Treap::value_type;
using pointer = typename std::conditional<Const,
const value_type*,
value_type*>::type;
using reference = typename std::conditional<Const,
const value_type&,
value_type&>::type;
using iterator_category = std::bidirectional_iterator_tag;
private:
node_ptr ptr_;
friend class Treap;
public:
explicit iterator_base(node_ptr ptr) : ptr_(ptr) {}
template<bool C>
iterator_base(const iterator_base<C>& rhs) : ptr_(rhs.ptr_) {}
template<bool C>
iterator_base& operator=(const iterator_base<C>& rhs) {
ptr_ = rhs.ptr_;
return *this;
}
template<bool C>
iterator_base(iterator_base<C>&& rhs) : ptr_(std::move(rhs.ptr_)) {}
template<bool C>
iterator_base& operator=(iterator_base<C>&& rhs) {
ptr_ = std::move(rhs.ptr_);
return *this;
}
template<bool C>
bool operator==(const iterator_base<C>& r) const {
return ptr_ == r.ptr_;
}
template<bool C>
bool operator!=(const iterator_base<C>& r) const {
return ptr_ != r.ptr_;
}
reference operator*() const { return ptr_->v; }
pointer operator->() const { return &(ptr_->v); }
iterator_base& operator++() {
auto u = ptr_;
if (u->right) {
u = u->right;
while (u->left)
u = u->left;
ptr_ = u;
} else {
node_ptr p;
while ((p = u->parent.lock()) and p->left != u) {
u = p;
}
assert(!u->parent.expired());
assert(u->parent.lock()->left == u);
ptr_ = u->parent.lock();
}
return *this;
}
iterator_base operator++(int) {
iterator ret = *this;
++*this;
return ret;
}
iterator_base& operator--() {
auto u = ptr_;
if (u->left) {
u = u->left;
while (u->right)
u = u->right;
ptr_ = u;
} else {
node_ptr p;
while ((p = u->parent.lock()) and p->right != u) {
u = p;
}
ptr_ = u->parent.lock();
}
return *this;
}
iterator_base operator--(int) {
iterator ret = *this;
--*this;
return ret;
}
};
public:
const_iterator begin() const {
auto u = sentinel_;
while (u->left)
u = u->left;
return const_iterator(u);
};
const_iterator end() const {
return const_iterator(sentinel_);
};
const_iterator cbegin() const {
return begin();
}
const_iterator cend() const {
return end();
}
iterator begin() {
return iterator(cbegin());
};
iterator end() {
return iterator(cend());
};
void print_for_debug(node_ptr u = nullptr, int depth = -1) const {
if (_root())
std::cout<<_root()->key()<<std::endl;
auto show = [&](auto& f, node_ptr u, int d) {
if (d >= depth)
return;
if (!u)
return;
std::cout << u->key() << std::endl;
if (u->left)
std::cout << u->left->key() << ' ';
else
std::cout << "--- ";
if (u->right)
std::cout << u->right->key() << std::endl;
else
std::cout << "---" << std::endl;
f(f, u->left, d+1);
f(f, u->right, d+1);
};
if (!u)
u = _root();
show(show, u, 0);
std::cout<<std::endl;
}
};
template<class T, class Compare=std::less<>>
using TreapSet = Treap<T, void, Compare>;
template<class T, class Compare=std::less<>>
using TreapMultiset = Treap<T, void, Compare, false>;
template<class T, class V, class Compare=std::less<>, bool UniqueKey=true>
class _TreapMap : public Treap<T, V, Compare, UniqueKey> {
static_assert(!std::is_same<V, void>::value, "");
using _base = Treap<T, V>;
public:
using typename _base::mapped_type;
using reference = mapped_type&;
reference operator[](const T& x) {
return _base::insert({x, mapped_type()}).first->second;
}
reference operator[](T&& x) {
return _base::insert({std::move(x), mapped_type()}).first->second;
}
};
template<class T, class V, class Compare=std::less<>>
using TreapMap = _TreapMap<T, V, Compare, true>;
template<class T, class V, class Compare=std::less<>>
using TreapMultimap = _TreapMap<T, V, Compare, false>;
namespace treap {
template<class T, class Compare=std::less<>>
using set = TreapSet<T, Compare>;
template<class T, class Compare=std::less<>>
using multiset = TreapMultiset<T, Compare>;
template<class T, class V, class Compare=std::less<>>
using map = TreapMap<T, V, Compare>;
template<class T, class V, class Compare=std::less<>>
using multimap = TreapMultimap<T, V, Compare>;
} // naamespace treap
#line 2 "include/mtl/bit_manip.hpp"
#include <cstdint>
#line 4 "include/mtl/bit_manip.hpp"
#if __cplusplus >= 202002L
#ifndef MTL_CPP20
#define MTL_CPP20
#endif
#include <bit>
#endif
namespace bm {
/// Count 1s for each 8 bits
inline constexpr uint64_t popcnt_e8(uint64_t x) {
x = (x & 0x5555555555555555) + ((x>>1) & 0x5555555555555555);
x = (x & 0x3333333333333333) + ((x>>2) & 0x3333333333333333);
x = (x & 0x0F0F0F0F0F0F0F0F) + ((x>>4) & 0x0F0F0F0F0F0F0F0F);
return x;
}
/// Count 1s
inline constexpr unsigned popcnt(uint64_t x) {
#ifdef MTL_CPP20
return std::popcount(x);
#else
return (popcnt_e8(x) * 0x0101010101010101) >> 56;
#endif
}
/// Alias to mtl::popcnt(x)
constexpr unsigned popcount(uint64_t x) {
return popcnt(x);
}
/// Count trailing 0s. s.t. *11011000 -> 3
inline constexpr unsigned ctz(uint64_t x) {
#ifdef MTL_CPP20
return std::countr_zero(x);
#else
return popcnt((x & (-x)) - 1);
#endif
}
/// Alias to mtl::ctz(x)
constexpr unsigned countr_zero(uint64_t x) {
return ctz(x);
}
/// Count trailing 1s. s.t. *11011011 -> 2
inline constexpr unsigned cto(uint64_t x) {
#ifdef MTL_CPP20
return std::countr_one(x);
#else
return ctz(~x);
#endif
}
/// Alias to mtl::cto(x)
constexpr unsigned countr_one(uint64_t x) {
return cto(x);
}
inline constexpr unsigned ctz8(uint8_t x) {
return x == 0 ? 8 : popcnt_e8((x & (-x)) - 1);
}
/// [00..0](8bit) -> 0, [**..*](not only 0) -> 1
inline constexpr uint8_t summary(uint64_t x) {
constexpr uint64_t hmask = 0x8080808080808080ull;
constexpr uint64_t lmask = 0x7F7F7F7F7F7F7F7Full;
auto a = x & hmask;
auto b = x & lmask;
b = hmask - b;
b = ~b;
auto c = (a | b) & hmask;
c *= 0x0002040810204081ull;
return uint8_t(c >> 56);
}
/// Extract target area of bits
inline constexpr uint64_t bextr(uint64_t x, unsigned start, unsigned len) {
uint64_t mask = len < 64 ? (1ull<<len)-1 : 0xFFFFFFFFFFFFFFFFull;
return (x >> start) & mask;
}
/// 00101101 -> 00111111 -count_1s-> 6
inline constexpr unsigned log2p1(uint8_t x) {
if (x & 0x80)
return 8;
uint64_t p = uint64_t(x) * 0x0101010101010101ull;
p -= 0x8040201008040201ull;
p = ~p & 0x8080808080808080ull;
p = (p >> 7) * 0x0101010101010101ull;
p >>= 56;
return p;
}
/// 00101100 -mask_mssb-> 00100000 -to_index-> 5
inline constexpr unsigned mssb8(uint8_t x) {
assert(x != 0);
return log2p1(x) - 1;
}
/// 00101100 -mask_lssb-> 00000100 -to_index-> 2
inline constexpr unsigned lssb8(uint8_t x) {
assert(x != 0);
return popcnt_e8((x & -x) - 1);
}
/// Count leading 0s. 00001011... -> 4
inline constexpr unsigned clz(uint64_t x) {
#ifdef MTL_CPP20
return std::countl_zero(x);
#else
if (x == 0)
return 64;
auto i = mssb8(summary(x));
auto j = mssb8(bextr(x, 8 * i, 8));
return 63 - (8 * i + j);
#endif
}
/// Alias to mtl::clz(x)
constexpr unsigned countl_zero(uint64_t x) {
return clz(x);
}
/// Count leading 1s. 11110100... -> 4
inline constexpr unsigned clo(uint64_t x) {
#ifdef MTL_CPP20
return std::countl_one(x);
#else
return clz(~x);
#endif
}
/// Alias to mtl::clo(x)
constexpr unsigned countl_one(uint64_t x) {
return clo(x);
}
inline constexpr unsigned clz8(uint8_t x) {
return x == 0 ? 8 : 7 - mssb8(x);
}
inline constexpr uint64_t bit_reverse(uint64_t x) {
x = ((x & 0x00000000FFFFFFFF) << 32) | ((x & 0xFFFFFFFF00000000) >> 32);
x = ((x & 0x0000FFFF0000FFFF) << 16) | ((x & 0xFFFF0000FFFF0000) >> 16);
x = ((x & 0x00FF00FF00FF00FF) << 8) | ((x & 0xFF00FF00FF00FF00) >> 8);
x = ((x & 0x0F0F0F0F0F0F0F0F) << 4) | ((x & 0xF0F0F0F0F0F0F0F0) >> 4);
x = ((x & 0x3333333333333333) << 2) | ((x & 0xCCCCCCCCCCCCCCCC) >> 2);
x = ((x & 0x5555555555555555) << 1) | ((x & 0xAAAAAAAAAAAAAAAA) >> 1);
return x;
}
/// Check if x is power of 2. 00100000 -> true, 00100001 -> false
constexpr bool has_single_bit(uint64_t x) noexcept {
#ifdef MTL_CPP20
return std::has_single_bit(x);
#else
return x != 0 && (x & (x - 1)) == 0;
#endif
}
/// Bit width needs to represent x. 00110110 -> 6
constexpr int bit_width(uint64_t x) noexcept {
#ifdef MTL_CPP20
return std::bit_width(x);
#else
return 64 - clz(x);
#endif
}
/// Ceil power of 2. 00110110 -> 01000000
constexpr uint64_t bit_ceil(uint64_t x) {
#ifdef MTL_CPP20
return std::bit_ceil(x);
#else
if (x == 0) return 1;
return 1ull << bit_width(x - 1);
#endif
}
/// Floor power of 2. 00110110 -> 00100000
constexpr uint64_t bit_floor(uint64_t x) {
#ifdef MTL_CPP20
return std::bit_floor(x);
#else
if (x == 0) return 0;
return 1ull << (bit_width(x) - 1);
#endif
}
} // namespace bm
#line 6 "include/mtl/integer_set.hpp"
#include <array>
#include <unordered_map>
#include <initializer_list>
#line 10 "include/mtl/integer_set.hpp"
template<typename T, unsigned BITS = 64>
class
[[deprecated("XFastTrie is expected to be used by YFastTrie. Single XFastTrie is inefficient for memory.")]]
_XFastTrie {
public:
using U = uint64_t;
static constexpr int W = BITS;
class iterator;
static constexpr bool kKeyOnly = std::is_same<T, void>::value;
using element_type = typename std::conditional<kKeyOnly, U, std::pair<U, T>>::type;
private:
struct Node;
using node_ptr = std::shared_ptr<Node>;
using node_weak = std::weak_ptr<Node>;
struct Node {
// common
uint8_t cmask;
std::array<node_ptr, 2> child;
node_weak parent;
// leaf
element_type* vptr;
Node() : cmask(0), child({nullptr, nullptr}), vptr(nullptr) {}
U key() const {
if constexpr (kKeyOnly)
return *vptr;
else
return vptr->first;
}
};
private:
using _hash_table = std::unordered_map<U, node_ptr>;
node_ptr root_, sentinel_;
size_t size_;
std::array<_hash_table, W+1> xmap_;
public:
_XFastTrie()
: root_(std::make_shared<Node>()), sentinel_(std::make_shared<Node>()), size_(0)
{
sentinel_->child[0] = sentinel_->child[1] = root_->child[0] = root_->child[1] = sentinel_;
xmap_[0].emplace(0, root_);
}
template<typename It>
explicit _XFastTrie(It begin, It end) : _XFastTrie() {
insert(begin, end);
}
_XFastTrie(std::initializer_list<element_type> list) : _XFastTrie(list.begin(), list.end()) {}
private:
void _del_node(node_ptr u) {
u->parent.reset();
for (int i = 0; i < 2; i++) {
if (u->cmask & (1<<i) and u->child[i] != u) {
_del_node(u->child[i]);
}
u->child[i] = nullptr;
}
if (u->vptr) {
delete u->vptr;
}
}
void _del() {
if (root_)
_del_node(root_);
if (sentinel_)
sentinel_->child[0] = sentinel_->child[1] = nullptr;
}
public:
// TODO: Optimal copy implementation
_XFastTrie(const _XFastTrie& r) : _XFastTrie(r.begin(), r.end()) {}
_XFastTrie& operator=(const _XFastTrie& r) {
_del();
root_ = std::make_shared<Node>();
sentinel_ = std::make_shared<Node>();
size_ = 0;
sentinel_->child[0] = sentinel_->child[1] =
root_->child[0] = root_->child[1] = sentinel_;
xmap_[0].emplace(0, root_);
insert(r.begin(), r.end());
return *this;
}
_XFastTrie(_XFastTrie&& r)
: root_(std::move(r.root_)), sentinel_(std::move(r.sentinel_)),
size_(std::move(r.size_)), xmap_(std::move(r.xmap_)) {}
_XFastTrie& operator=(_XFastTrie&& r) noexcept {
_del();
root_ = std::move(r.root_);
sentinel_ = std::move(r.sentinel_);
size_ = std::move(r.size_);
xmap_ = std::move(r.xmap_);
return *this;
}
~_XFastTrie() {
_del();
}
size_t size() const { return size_; }
bool empty() const { return size() == 0; }
void clear() {
*this = _XFastTrie();
}
iterator find(U x) const {
auto it = xmap_[W].find(x);
return it != xmap_[W].end() ? iterator(it->second) : end();
}
size_t count(U x) const { return (size_t) (find(x) != end()); }
bool contains(U x) const { return (bool) count(x); }
iterator lower_bound(U x) const {
int l = 0, r = W+1;
auto u = root_;
while (l+1<r) {
int c = (l+r)/2;
auto vit = xmap_[c].find(x >> (W-c));
if (vit != xmap_[c].end()) {
u = vit->second;
l = c;
} else {
r = c;
}
}
if (l == W) return iterator(u);
auto next = ((x>>(W-1-l))&1) == 0 ? u->child[0] : u->child[1]->child[1];
return iterator(next);
}
iterator upper_bound(U x) const {
auto it = lower_bound(x);
return (it != end() and it.ptr_->key() == x) ? ++it : it;
}
iterator successor(U x) const {
return upper_bound(x);
}
iterator predecessor(U x) const {
auto it = lower_bound(x);
return it != begin() ? --it : end();
}
private:
U _key_of_elm(element_type& e) const {
if constexpr (kKeyOnly)
return e;
else
return e.first;
}
U _key_of(iterator it) const {
return _key_of_elm(*(it.ptr_->vptr));
}
template<typename... Args>
U _key_of_elm_args(U x, Args&&...) const { return x; }
iterator _insert_subtree(int depth, node_ptr u, U x, element_type* eptr) {
int i = depth;
int c = (x >> (W-i-1)) & 1;
auto pred = c == 1 ? u->child[1] : u->child[0]->child[0];
assert(pred);
for (; i < W; i++) {
c = (x >> (W-1-i)) & 1;
u->cmask |= 1u<<c;
u->child[c] = std::make_shared<Node>();
u->child[c]->parent = u;
u = u->child[c];
xmap_[i+1].emplace(x>>(W-1-i), u);
}
u->vptr = eptr;
u->child[0] = pred;
u->child[1] = pred->child[1];
pred->child[1]->child[0] = u;
pred->child[1] = u;
auto v = u->parent.lock();
for (i = W-1; i >= 0; i--) {
assert(v);
c = (x >> (W-1-i)) & 1;
int ic = c^1;
if ((v->cmask & (1u<<ic)) == 0
and (!v->child[ic] or v->child[ic] == sentinel_
or (ic == 0 ? v->child[ic]->key() > x
: v->child[ic]->key() < x)))
v->child[ic] = u;
assert(v->child[0] and v->child[1]);
v = v->parent.lock();
}
size_++;
return iterator(u);
}
iterator _insert(U x, element_type* eptr) {
auto u = root_;
int i, c;
for (i = 0; i < W; i++) {
c = (x >> (W-1-i)) & 1;
if ((u->cmask & (1u<<c)) == 0) break;
u = u->child[c];
}
if (i == W) return iterator(u);
return _insert_subtree(i, u, x, eptr);
}
iterator _insert_hint(iterator hint, U x, element_type* eptr) {
// Check hint isn't malicious.
U lx=0, rx=0;
if ((hint != begin() and x < (lx = _key_of(std::prev(hint)))) or
(hint != end() and (rx = _key_of(hint)) < x))
return _insert(x, eptr);
// Find longest common path on the trie.
int d = 0;
if (hint != begin())
d = std::max(d, (int) bm::clz(x ^ lx) - (64-W));
if (hint != end())
d = std::max(d, (int) bm::clz(x ^ rx) - (64-W));
if (d == W) return iterator(xmap_[W][x]);
return _insert_subtree(d, xmap_[d][x >> (W-d)], x, eptr);
}
public:
iterator insert(const element_type& e) {
return _insert(_key_of_elm(e),
new element_type(e));
}
iterator insert(element_type&& e) {
return _insert(_key_of_elm(e),
new element_type(std::move(e)));
}
template<typename... Args>
iterator emplace(Args&&... args) {
return _insert(_key_of_elm_args(args...),
new element_type(std::forward<Args>(args)...));
}
template<typename... Args>
iterator emplace_hint(iterator hint, Args&&... args) {
return _insert_hint(hint,
_key_of_elm_args(args...),
new element_type(std::forward<Args>(args)...));
}
template<typename It>
void insert(It begin, It end) {
using traits = std::iterator_traits<It>;
static_assert(std::is_convertible<typename traits::value_type, element_type>::value, "");
static_assert(std::is_base_of<std::forward_iterator_tag, typename traits::iterator_category>::value, "");
for (auto it = begin; it != end; ++it)
insert(*it);
}
void insert(std::initializer_list<element_type> list) {
insert(list.begin(), list.end());
}
iterator erase(iterator it) {
if (it == end())
return it;
auto u = it.ptr_;
U x = u->key();
delete u->vptr;
auto next = u->child[0];
u->child[0]->child[1] = u->child[1];
u->child[1]->child[0] = u->child[0];
auto v = u;
int i, c;
for (i = W-1; i >= 0; i--) {
c = (x >> (W-1-i)) & 1;
auto p = v->parent.lock();
v->parent.reset();
p->cmask ^= 1u<<c;
p->child[c] = nullptr;
assert(xmap_[i+1].find(x>>(W-1-i))->second == v);
xmap_[i+1].erase(x>>(W-1-i));
v = p;
if ((p->cmask & (1u<<(c^1))) != 0) break;
}
if (i >= 0) {
c = (x >> (W-1-i)) & 1;
v->child[c] = u->child[c^1];
v = v->parent.lock();
i--;
for (; i >= 0; i--) {
c = (x >> (W-1-i)) & 1;
int ic = c^1;
if (v->child[ic] == u) {
v->child[ic] = u->child[c];
}
v = v->parent.lock();
}
}
size_--;
return iterator(next);
}
iterator erase(U x) {
auto it = lower_bound(x);
if (it.key() != x)
return it;
return erase(it);
}
public:
class iterator {
public:
using value_type = element_type;
using pointer = element_type*;
using reference = const element_type&;
using difference_type = long long;
using iterator_category = std::bidirectional_iterator_tag;
private:
node_ptr ptr_;
friend class _XFastTrie;
public:
explicit iterator(node_ptr ptr) : ptr_(ptr) {}
reference operator*() const { return *(ptr_->vptr); }
pointer operator->() const { return ptr_->vptr; }
bool operator==(const iterator& r) const { return ptr_ == r.ptr_; }
bool operator!=(const iterator& r) const { return ptr_ != r.ptr_; }
iterator& operator++() {
ptr_ = ptr_->child[1];
return *this;
}
iterator operator++(int) {
iterator ret = *this;
++*this;
return ret;
}
iterator& operator--() {
ptr_ = ptr_->child[0];
return *this;
}
iterator operator--(int) {
iterator ret = *this;
--*this;
return ret;
}
U key() const { return ptr_->key(); }
};
iterator begin() const { return iterator(sentinel_->child[1]); }
iterator end() const { return iterator(sentinel_); }
};
template<typename T, unsigned BITS>
constexpr int _XFastTrie<T, BITS>::W;
template<typename T, unsigned BITS>
constexpr bool _XFastTrie<T, BITS>::kKeyOnly;
template<unsigned BITS = 64>
using XFastTrieSet = _XFastTrie<void, BITS>;
template<typename T, unsigned BITS = 64>
using XFastTrieMap = _XFastTrie<T, BITS>;
template<typename T, unsigned BITS=64>
class YFastTrie {
public:
using U = uint64_t;
static constexpr int W = BITS;
static constexpr U MAX_KEY = W == 64 ? ~uint64_t(0) : (1ull<<W)-1;
static constexpr bool kKeyOnly = std::is_same<T, void>::value;
using element_type = typename std::conditional<kKeyOnly, U, std::pair<U,T>>::type;
using value_type = typename std::conditional<kKeyOnly, U, T>::type;
using _set = typename std::conditional<kKeyOnly, TreapSet<U>, TreapMap<U,T>>::type;
using _set_iterator = typename _set::iterator;
using _xft = XFastTrieMap<_set, W>;
class iterator;
private:
_xft xft_;
size_t size_;
bool _pibot_selected() {
return rand() % W == 0;
}
U _key_of_elm(const element_type& e) const {
if constexpr (kKeyOnly)
return e;
else
return e.first;
}
U _key_of_elm(element_type&& e) const {
if constexpr (kKeyOnly)
return e;
else
return e.first;
}
template<typename... Args>
U _key_of_elm_args(U x, Args&&...) const {
return x;
}
U _key_of_sub(_set_iterator it) const {
return _key_of_elm(*it);
}
U _key_of(iterator it) const {
return _key_of_sub(it.sit_);
}
public:
YFastTrie() : size_(0) {
xft_.emplace(MAX_KEY, _set{});
}
template<typename It>
explicit YFastTrie(It begin, It end) : YFastTrie() {
insert(begin, end);
}
YFastTrie(std::initializer_list<element_type> list) : YFastTrie(list.begin(), list.end()) {}
size_t size() const { return size_; }
bool empty() const { return size() == 0; }
void clear() {
*this = YFastTrie();
}
iterator find(U x) const {
auto xit = xft_.lower_bound(x);
assert(xit != xft_.end());
auto& s = xit->second;
auto sit = s.find(x);
return sit != s.end() ? iterator(this, xit, sit) : end();
}
size_t count(U x) const { return (size_t) (find(x) != end()); }
bool contains(U x) const { return (bool) count(x); }
iterator lower_bound(U x) const {
auto xit = xft_.lower_bound(x);
assert(xit != xft_.end());
auto& s = xit->second;
auto sit = s.lower_bound(x);
if (sit == s.end()) {
assert(std::next(xit) == xft_.end());
return end();
}
return iterator(this, xit, sit);
}
iterator upper_bound(U x) const {
auto it = lower_bound(x);
return (it != end() and _key_of(it) == x) ? ++it : it;
}
iterator successor(U x) const {
return upper_bound(x);
}
iterator predecessor(U x) const {
auto it = lower_bound(x);
return it != begin() ? --it : end();
}
private:
template<typename C>
iterator _insert_before(typename _xft::iterator xit, _set_iterator sit, U x, C elm_constructor) {
auto& s = xit->second;
// Expect 'sit = s.emplace_hint(sit, element)'
sit = elm_constructor(s, sit);
size_++;
if (_pibot_selected()) {
xit = xft_.emplace_hint(xit, x, _set());
xit->second = s.split(std::next(sit));
}
return iterator(this, xit, sit);
}
template<typename C>
iterator _insert(U x, C elm_constructor) {
auto xit = xft_.lower_bound(x);
assert(xit != xft_.end());
auto& s = xit->second;
auto sit = s.lower_bound(x);
if (sit == s.end() or _key_of_sub(sit) > x) {
return _insert_before(xit, sit, x, elm_constructor);
}
return iterator(this, xit, sit);
}
template<typename C>
iterator _insert_hint(iterator hint, U x, C elm_constructor) {
// Check hint isn't malicious.
if ((hint != begin() and x <= _key_of(std::prev(hint))) or
(hint != end() and _key_of(hint) <= x))
return _insert(x, elm_constructor);
auto xit = hint.xit_;
assert(xit != xft_.end());
auto sit = hint.sit_;
assert(sit == xit->second.end() or _key_of_sub(sit) > x);
return _insert_before(xit, sit, x, elm_constructor);
}
public:
iterator insert(const element_type& e) {
return _insert(_key_of_elm(e),
[&e]
(_set& s, const _set_iterator& it) {
return s.emplace_hint(it, e);
});
}
iterator insert(element_type&& e) {
return _insert(_key_of_elm(e),
[e=std::move(e)](_set& s, const _set_iterator& it) {
return s.emplace_hint(it, std::move(e));
});
}
template<typename... Args>
iterator emplace(Args&&... args) {
return _insert(_key_of_elm_args(args...),
[&args...](_set& s, const _set_iterator& it) {
return s.emplace_hint(it, std::forward<Args>(args)...);
});
}
template<typename... Args>
iterator emplace_hint(iterator hint, Args&&... args) {
return _insert_hint(hint,
_key_of_elm_args(args...),
[&args...](_set& s, const _set_iterator& it) {
return s.emplace_hint(it, std::forward<Args>(args)...);
});
}
template<typename It>
void insert(It begin, It end) {
using traits = std::iterator_traits<It>;
static_assert(std::is_convertible<typename traits::value_type, element_type>::value, "");
static_assert(std::is_base_of<std::forward_iterator_tag, typename traits::iterator_category>::value, "");
for (auto it = begin; it != end; ++it)
insert(*it);
}
void insert(std::initializer_list<element_type> list) {
insert(list.begin(), list.end());
}
iterator erase(iterator it) {
if (it == end())
return it;
U x = _key_of(it);
auto xit = it.xit_;
assert(xit != xft_.end());
auto& s = xit->second;
auto sit = it.sit_;
size_--;
sit = s.erase(sit);
if (x == xit.key()) {
if (x != MAX_KEY) {
if (!s.empty()) {
auto& snext = std::next(xit)->second;
sit = snext.absorb(&s);
}
xit = xft_.erase(xit);
} else {
return end();
}
}
return iterator(this, xit, sit);
}
iterator erase(U x) {
auto it = lower_bound(x);
return (_key_of(it) == x) ? erase(it) : it;
}
public:
class iterator {
public:
using value_type = element_type;
using pointer = element_type*;
using reference = const element_type&;
using difference_type = long long;
using iterator_category = std::bidirectional_iterator_tag;
using xiterator = typename _xft::iterator;
using siterator = _set_iterator;
private:
const YFastTrie* yft_;
xiterator xit_;
siterator sit_;
friend class YFastTrie;
public:
iterator(const YFastTrie* yft, xiterator xit, siterator sit) : yft_(yft), xit_(xit), sit_(sit) {}
reference operator*() const { return *sit_; }
pointer operator->() const { return &*sit_; }
bool operator==(const iterator& r) { return sit_ == r.sit_; }
bool operator!=(const iterator& r) { return sit_ != r.sit_; }
iterator& operator++() {
if (++sit_ == xit_->second.end()) {
auto nxt = std::next(xit_);
if (nxt != yft_->xft_.end()) {
xit_ = nxt;
sit_ = xit_->second.begin();
}
}
return *this;
}
iterator operator++(int) {
iterator ret = *this;
++this;
return ret;
}
iterator& operator--() {
if (sit_ == xit_->second.begin()) {
--xit_;
sit_ = std::prev(xit_->second.end());
} else {
--sit_;
}
return *this;
}
iterator operator--(int) {
iterator ret = *this;
--this;
return ret;
}
};
iterator begin() const {
auto xit = xft_.begin();
return iterator(this, xit, xit->second.begin());
}
iterator end() const {
auto xit = std::prev(xft_.end());
return iterator(this, xit, xit->second.end());
}
};
template<typename T, unsigned BITS>
constexpr int YFastTrie<T, BITS>::W;
template<typename T, unsigned BITS>
constexpr typename YFastTrie<T, BITS>::U YFastTrie<T, BITS>::MAX_KEY;
template<typename T, unsigned BITS>
constexpr bool YFastTrie<T, BITS>::kKeyOnly;
template<unsigned BITS=64>
using YFastTrieSet = YFastTrie<void, BITS>;
template<typename T, unsigned BITS=64>
class YFastTrieMAP : public YFastTrie<T, BITS> {
using _base = YFastTrie<T, BITS>;
public:
using typename _base::value_type;
using typename _base::U;
using _base::kKeyOnly;
using reference = value_type&;
reference operator[](U x) {
auto it = find(x);
if (it == _base::end())
it = emplace(x);
if constexpr (kKeyOnly)
return *it;
else
return it->second;
}
};
#line 2 "test/standalone/set_test.hpp"
#include <vector>
#include <algorithm>
#include <type_traits>
#line 6 "test/standalone/set_test.hpp"
#include <set>
namespace mtl {
using std::cout;
using std::cerr;
using std::endl;
template<class Map>
void map_emplace_test() {
using key_type = typename Map::key_type;
using mapped_type = typename Map::mapped_type;
Map s;
s.emplace(std::make_pair(key_type(), mapped_type()));
s.emplace(key_type(), mapped_type());
}
template<class Set, int Max = (int)4e5, bool Shuffle = true>
void integer_set_test() {
std::vector<int> values;
while (values.empty()) {
for (int i = 0; i < Max; i++)
if (rand()%4 == 0)
values.push_back(i);
}
int n = values.size();
auto insertions = values;
if constexpr (Shuffle)
std::random_shuffle(insertions.begin(), insertions.end());
Set S(insertions.begin(), insertions.end());
if (values != std::vector<int>(S.begin(), S.end())) {
cout << "after insert order broken" << endl;
exit(EXIT_FAILURE);
}
// S.print_for_debug();
int target = -1;
int pred = -1;
int succ = values[0];
int k = 0;
auto log = [&]() {
std::cout << pred << ' ' << target << ' ' << succ << std::endl;
};
for (int i = 0; i < Max; i++) {
if (k < n and values[k] == i) {
target = values[k];
pred = k-1 >= 0 ? values[k-1] : -1;
succ = k+1 < n ? values[k+1] : -1;
k++;
} else {
pred = k-1 >= 0 ? values[k-1] : -1;
target = -1;
}
auto fit = S.find(i);
if (fit != S.end()) {
if ((int)*fit != i) {
std::cout << "find: " << i << std::endl;
log();
exit(EXIT_FAILURE);
}
} else {
if (target != -1) {
log();
exit(EXIT_FAILURE);
}
}
auto sucit = S.upper_bound(i);
if (sucit != S.end()) {
if ((int)*sucit != succ) {
std::cout << "succ: " << *sucit << std::endl;
log();
exit(EXIT_FAILURE);
}
} else {
if (succ != -1) {
log();
exit(EXIT_FAILURE);
}
}
auto predit = S.lower_bound(i);
if (predit != S.begin()) {
--predit;
if ((int)*predit != pred) {
std::cout << "pred: " << *predit << std::endl;
log();
exit(EXIT_FAILURE);
}
} else {
if (pred != -1) {
log();
exit(EXIT_FAILURE);
}
}
}
int size = n;
if ((int) S.size() != size) {
std::cout << S.size() << ' ' << size<< std::endl;
log();
exit(EXIT_FAILURE);
}
for (int v : insertions) {
auto f = S.find(v);
assert(f != S.end());
auto p = f;
auto m = std::next(f);
for (int i = 0; i < 2 and p != S.begin(); i++)
--p;
for (int i = 0; i < 2 and m != S.end(); i++)
++m;
std::vector<unsigned> o(p,m);
o.erase(find(o.begin(), o.end(), v));
S.erase(v);
size--;
{
auto lb = S.lower_bound(v);
auto p = lb, m = lb;
for (int i = 0; i < 2 and p != S.begin(); i++)
--p;
for (int i = 0; i < 2 and m != S.end(); i++)
++m;
if (o != std::vector<unsigned>(p,m)) {
std::cout << n-size<<" after erase "<<v<<" order broken " << endl;
for (auto v:o)
cerr<<v<<' ';
cerr<<endl;
for (auto it = p; it != m; ++it) {
cerr<<*it<<' ';
}
cerr<<endl;
exit(EXIT_FAILURE);
}
}
if ((int) S.size() != size) {
std::cout << S.size() << ' ' << size<< std::endl;
exit(EXIT_FAILURE);
}
}
cerr<<"integer_set_test ok"<<endl;
}
}
#line 4 "test/standalone/integer_set_test.cpp"
constexpr int W = 20;
//constexpr int Max = 4e5;
//
//template<typename Set>
//int test_set() {
// std::vector<int> values;
// while (values.empty()) {
// for (int i = 0; i < Max; i++) {
// if (i == 0 or rand()%4 == 0)
// values.push_back(i);
// }
// }
// int n = values.size();
// std::vector<int> shuffled = values;
// for (int i = 0; i < n; i++) {
// std::swap(shuffled[i], shuffled[rand()%n]);
// }
//
// Set S;
// for (int v : shuffled) {
// S.insert(v);
// }
//// S.print_for_debug();
// int target = -1;
// int pred = -1;
// int succ = values[0];
// int k = 0;
// auto log = [&]() {
// std::cout << pred << ' ' << target << ' ' << succ << std::endl;
// assert(false);
// };
// for (int i = 0; i < Max; i++) {
// if (k < n and values[k] == i) {
// target = values[k];
// pred = k-1 >= 0 ? values[k-1] : -1;
// succ = k+1 < n ? values[k+1] : -1;
// k++;
// } else {
// pred = k-1 >= 0 ? values[k-1] : -1;
// target = -1;
// }
//
// auto fit = S.find(i);
// if (fit != S.end()) {
// if ((int) *fit != i) {
// std::cout << "find: " << i << std::endl;
// log();
// return 1;
// }
// } else {
// if (target != -1) {
// log();
// return 1;
// }
// }
//
// auto sucit = S.successor(i);
// if (sucit != S.end()) {
// if ((int) *sucit != succ) {
// std::cout << "succ: " << *sucit << std::endl;
// log();
// return 1;
// }
// } else {
// if (succ != -1) {
// log();
// return 1;
// }
// }
//
// auto predit = S.predecessor(i);
// if (predit != S.end()) {
// if ((int) *predit != pred) {
// std::cout << "pred: " << *predit << std::endl;
// log();
// return 1;
// }
// } else {
// if (pred != -1) {
// log();
// return 1;
// }
// }
// }
//
// int size = n;
// if ((int) S.size() != size) {
// std::cout << S.size() << ' ' << size<< std::endl;
// log();
// return 1;
// }
// for (int v : shuffled) {
// S.erase(v);
// size--;
// if ((int) S.size() != size) {
// std::cout << S.size() << ' ' << size<< std::endl;
// assert(false);
// return 1;
// }
// }
// return 0;
//}
int main() {
// mtl::integer_set_test<XFastTrieSet<W>>();
// mtl::integer_set_test<YFastTrieSet<W>>();
std::cout << "OK" << std::endl;
}