This documentation is automatically generated by online-judge-tools/verification-helper
#include "src/datastructure/radixheap.hpp"
// D.key must be unsigned integer
template <class D> struct RadixHeap {
using C = typename make_unsigned<decltype(D().key)>::type;
static int bsr1(C x) { return (x == 0) ? 0 : bsr(x) + 1; }
size_t sz = 0, cnt = 0;
C last = 0;
VV<D> v = VV<D>(sizeof(C) * 8 + 1);
RadixHeap() {}
void push(D x) {
assert(decltype(x.key)(last) <= x.key);
sz++;
v[bsr1(x.key ^ last)].push_back(x);
}
void pull() {
if (cnt < v[0].size()) return;
int i = 1;
while (v[i].empty()) i++;
last = min_element(v[i].begin(), v[i].end(), [&](D l, D r) {
return l.key < r.key;
})->key;
for (D x : v[i]) {
v[bsr1(x.key ^ last)].push_back(x);
}
v[i].clear();
}
D top() {
pull();
return v[0][cnt];
}
void pop() {
pull();
sz--;
cnt++;
}
size_t size() const { return sz; }
bool empty() const { return sz == 0; }
};
#line 1 "src/datastructure/radixheap.hpp"
// D.key must be unsigned integer
template <class D> struct RadixHeap {
using C = typename make_unsigned<decltype(D().key)>::type;
static int bsr1(C x) { return (x == 0) ? 0 : bsr(x) + 1; }
size_t sz = 0, cnt = 0;
C last = 0;
VV<D> v = VV<D>(sizeof(C) * 8 + 1);
RadixHeap() {}
void push(D x) {
assert(decltype(x.key)(last) <= x.key);
sz++;
v[bsr1(x.key ^ last)].push_back(x);
}
void pull() {
if (cnt < v[0].size()) return;
int i = 1;
while (v[i].empty()) i++;
last = min_element(v[i].begin(), v[i].end(), [&](D l, D r) {
return l.key < r.key;
})->key;
for (D x : v[i]) {
v[bsr1(x.key ^ last)].push_back(x);
}
v[i].clear();
}
D top() {
pull();
return v[0][cnt];
}
void pop() {
pull();
sz--;
cnt++;
}
size_t size() const { return sz; }
bool empty() const { return sz == 0; }
};