matsutaku-library
This documentation is automatically generated by competitive-verifier/competitive-verifier
test/succinct/wavelet_tree_test.cpp
- View this file on GitHub
- Last update: 2024-07-11 22:21:57+09:00
Code
#define STANDALONE
#include "include/mtl/succinct/wavelet_tree.hpp"
#include <bits/stdc++.h>
using namespace std;
int main() {
const int n = 1e6;
std::vector<char> S(n);
std::array<int, 26> cnt{};
std::array<std::vector<int>, 26> rank, select, rank_c;
for (int i = 0; i < 26; i++) {
rank[i].resize(n+1);
rank_c[i].resize(n+1);
}
for (int i = 0; i < n; i++) {
int c = rand()%26;
S[i] = c;
for (int j = 0; j < 26; j++) {
rank[j][i] = cnt[j];
if (j) rank_c[j][i] = rank_c[j-1][i] + cnt[j-1];
}
cnt[c]++;
select[c].push_back(i);
}
for (int i = 0; i < 26; i++) {
rank[i][n] = cnt[i];
if (i) rank_c[i][n] = rank_c[i-1][n] + cnt[i-1];
select[i].push_back(n);
}
WaveletTree<char> wm(S.begin(), S.end());
// access
for (int i = 0; i < n; i++) {
char v = wm.get(i);
if (v != S[i]) {
cout << "Failed access "<<i<<" wm.get: "<<char(v+'a')<<" != S: "<<char(S[i]+'a')<<endl;
return 1;
}
}
// rank
for (int i = 0; i <= n; i++) {
for (int c = 0; c < 26; c++) {
int v = wm.rank(c, i);
if (v != rank[c][i]) {
cout << "Failed rank "<<char(c+'a')<<", "<<i<<" wm.rank: "<<v<<" != rank: "<<rank[c][i]<<endl;
return 1;
}
}
}
// select
std::array<int, 26> selected{};
for (int i = 0; i < n; i++) {
int c = S[i];
int k = selected[c]++;
int v = wm.select(c, k);
if (v != select[c][k] or v != i) {
cout << "Failed select "<<char(S[i]+'a')<<", "<<k<<" wm.select: "<<v<<" != select: "<<select[c][k]<<endl;
return 1;
}
}
for (int c = 0; c < 26; c++) {
int k = selected[c];
int v = wm.select(c, k);
if (v != select[c][k] or v != n) {
cout << "Failed select "<<char(c + 'a')<<", "<<k<<" wm.select: "<<v<<" != select: "<<select[c][k]<<endl;
return 1;
}
}
// rank_c
for (int i = 0; i <= n; i++) {
for (int c = 0; c < 26; c++) {
int v = wm.rank_lower(c, i);
if (v != rank_c[c][i]) {
cout << "Failed rank_c "<<char(c+'a')<<", "<<i<<" wm.rank_lower: "<<v<<" != rank_c: "<<rank_c[c][i]<<endl;
return 1;
}
}
}
// enumerate
const int m = std::min(n, (int)cbrt(n*6));
for (int l = 0; l < m; l++) {
for (int r = l+1; r <= m; r++) {
std::array<int, 26> enm{};
for (int c = 0; c < 26; c++) enm[c] = rank[c][r] - rank[c][l];
auto _v = wm.enumerate(l, r);
std::array<int, 26> v{};
for (auto p : _v) v[p.first] = p.second;
for (int c = 0; c < 26; c++) {
if (v[c] != enm[c]) {
cout << "Failed enumerate "<<l<<", "<<r<<", "<<char(c+'a')<<" wm.enumerate: "<<v[c]<<" != "<<enm[c]<<endl;
return 1;
}
}
}
}
std::cout << "OK" << std::endl;
}#line 1 "test/succinct/wavelet_tree_test.cpp"
#define STANDALONE
#line 2 "include/mtl/succinct/wavelet_tree.hpp"
#include <limits>
#include <array>
#include <iterator>
#include <algorithm>
#include <queue>
#include <tuple>
#line 2 "include/mtl/bit_manip.hpp"
#include <cstdint>
#include <cassert>
#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 4 "include/mtl/succinct/select.hpp"
struct select64 {
using size_type = uint8_t;
static struct make_select_table {
using bitmap_type = uint8_t;
std::array<std::array<size_type, 9>, 1<<8> tb;
make_select_table() {
for (int i = 0; i < 1<<8; i++) {
int c = 0;
int x = i;
tb[i].fill(8);
for (int j = 0; j < 8; j++) {
if (x & 1)
tb[i][++c] = j;
x >>= 1;
}
}
}
size_type operator()(bitmap_type bitmap, size_type ith) const {
return tb[bitmap][ith];
}
} sel_tb;
template<bool B>
static constexpr size_type select(size_type ith, uint64_t bitmap) { // 0-indexed
assert(ith < 64);
ith++; // to 1-index
// Find byte
uint64_t w = bitmap;
if constexpr (!B) w = ~w;
auto _bs = (uint64_t) bm::popcnt_e8(w) * 0x0101010101010100ull;
auto bs = (const uint8_t*) &_bs;
size_type b = 0;
auto o = ith;
/* Following bit-manipulates code is same as ... */
// {
// auto d = 8;
// while (d > 1) {
// auto c = b + d/2;
// if (bs[c] < o)
// b = c;
// d /= 2;
// }
// }
{
uint64_t x = (uint64_t) o * 0x0101010101010101ull;
uint64_t bmx = (_bs | 0x8080808080808080ull) - x;
uint64_t y = ((bmx & 0x8080808080808080ull) * 0x02040810204081ull) >> (64-8);
size_type nb = bm::ctz8(y) - 1;
// assert(b == nb);
b = nb;
}
// Calc select
auto r = o - bs[b];
uint8_t byte = ((const uint8_t*)(&w))[b];
assert(r and r <= (size_type)bm::popcnt(byte));
return b * 8 + sel_tb(byte, r);
}
static constexpr size_type select1(size_type ith, uint64_t bitmap) {
return select<1>(ith, bitmap);
}
static constexpr size_type select0(size_type ith, uint64_t bitmap) {
return select<0>(ith, bitmap);
}
};
typename select64::make_select_table select64::sel_tb;
#line 3 "include/mtl/succinct/bv.hpp"
#include <vector>
#include <cstddef>
#line 6 "include/mtl/succinct/bv.hpp"
#include <bitset>
#include <iostream>
#if __cpp_concepts >= 202002L
#include <concepts>
template<class T>
concept ConstructableBV = requires(T t, size_t s) {
{ t.size() } -> std::same_as<size_t>;
{ t.word_size() } -> std::same_as<size_t>;
{ t.get_word(s) } -> std::convertible_to<uint64_t>;
};
#endif
template<
#if __cpp_concepts >= 202002L
ConstructableBV
#else
class
#endif
BitVec, unsigned WordSize>
struct BV {
static_assert(WordSize <= 64, "WordSize must be <= 64");
static constexpr unsigned S = WordSize;
static constexpr unsigned S_PER_L = 8;
static constexpr unsigned L = S*S_PER_L;
using bitvec_type = BitVec;
const bitvec_type* bm_;
std::vector<uint64_t> _r, _s, _zs;
BV() = default;
explicit BV(const bitvec_type* bm) {
build(bm);
}
void set_ptr(const bitvec_type* bm) {
bm_ = bm;
}
void build(const bitvec_type* bm) {
set_ptr(bm);
const auto num_l = (bm->size() + L-1) / L;
_r.assign((num_l + 1) * 2, 0);
_s.clear();
_s.push_back(0);
_zs.clear();
_zs.push_back(0);
uint64_t sum = 0;
for (size_t l = 0; l < num_l; ++l) {
auto psum = sum;
uint64_t sum_l = 0;
for (size_t s = 0; s < S_PER_L; ++s) {
if (l * S_PER_L + s < bm->word_size())
sum_l += bm::popcnt(bm->get_word(l * S_PER_L + s));
if (s < S_PER_L-1)
_r[l * 2 + 1] |= sum_l << ((7-(s+1)) * 9);
}
sum += sum_l;
_r[(l + 1) * 2] = sum;
if (psum / L != sum / L) {
_s.push_back(l);
}
if ((L*l - psum) / L != (L*(l+1) - sum) / L) {
_zs.push_back(l);
}
}
_s.push_back(num_l);
_zs.push_back(num_l);
}
template<bool B>
size_t get_l(size_t l) const {
auto b = _r[l*2];
return B ? b : l * L - b;
}
static constexpr size_t s_off(size_t s) {
return (7-s) * 9;
}
template<bool B>
size_t get_s(size_t l, size_t s) const {
auto b = (_r[l*2+1] >> s_off(s)) % (1ull<<9);
return B ? b : s * S - b;
}
uint64_t mask(size_t width) const {
return width == 64 ? ~0ull : (1ull << width) - 1;
}
size_t rank1(size_t i) const {
auto l = i / L;
auto s = i % L / S;
auto q = i / S;
auto r = i % S;
assert(bm_ != nullptr);
auto w = bm_->get_word(q) & mask(r);
return get_l<1>(l) +
get_s<1>(l, s) +
bm::popcnt(w);
}
size_t rank0(size_t i) const {
return i - rank1(i);
}
template<bool B>
size_t rank(size_t i) const {
if constexpr (B)
return rank1(i);
else
return rank0(i);
}
static struct l_block_cap_mask {
uint64_t mask;
constexpr l_block_cap_mask() : mask(0) {
for (unsigned i = 0; i < S_PER_L; i++) {
uint64_t cap = i * S;
mask |= cap << s_off(i);
}
}
} l_block_cap;
template<bool B>
size_t select(size_t ith) const {
auto n = ith+1; // to 1-indexed
if (n > rank<B>(bm_->size()))
return bm_->size();
// Find L block
auto& idx = B ? _s : _zs;
size_t l = idx[n / L];
{
auto r = idx[n / L + 1] + 1;
while (l+1 < r) {
auto c = l + (r-l)/2;
if (get_l<B>(c) < n)
l = c;
else
r = c;
}
}
// Find S block
size_t s = 0;
auto m = n - get_l<B>(l);
/* Following bit-manipulates code is same as ... */
// {
// auto d = 8;
// while (d > 1) {
// auto c = s + d/2;
// if (get_s<B>(l, c) < m)
// s = c;
// d /= 2;
// }
// }
{
uint64_t x = (uint64_t) (m-1) * 0x0040201008040201ull;
uint64_t a = _r[l*2+1];
if constexpr (!B)
a = l_block_cap.mask - a; // to 0s sum
uint64_t xda = x - a;
uint64_t sm = 0x4020100804020100ull;
uint64_t ok = (~x | a) & sm;
uint64_t ng = (~x & a) & sm;
uint64_t y = ((x ^ a ^ xda) & ok) | ng;
y = y * 0x0001010101010101ull >> (64-1-7);
auto id = bm::clz8(y)-1;
auto clo = bm::clz((~xda << 1 | 1) << (9*id));
auto ns = id + (clo ? (clo - 1) / 9 : 0);
s = ns;
}
// Calc select
auto o = m - get_s<B>(l, s);
uint64_t w = bm_->get_word(l * S_PER_L + s);
return l * L +
s * S +
select64::select<B>(o-1, w);
}
size_t select1(size_t ith) const {
return select<1>(ith);
}
size_t select0(size_t ith) const {
return select<0>(ith);
}
};
template<class BitVec, unsigned WordSize>
typename BV<BitVec, WordSize>::l_block_cap_mask BV<BitVec, WordSize>::l_block_cap;
#line 9 "include/mtl/succinct/bitmap.hpp"
auto t = std::iterator_traits<std::vector<bool>::iterator>::iterator_category();
/// Bitmap is likes std::vector<bool> with advanced operations
struct Bitmap {
using value_type = bool;
using W = uint64_t;
std::vector<W> arr;
size_t sz;
static constexpr size_t required_word_size(size_t n) {
return (n+63) / 64;
}
static constexpr W word_filled_by(bool bit) {
return bit ? 0xFFFFFFFFFFFFFFFF : 0;
}
explicit Bitmap(size_t n = 0, bool bit = false)
: arr(required_word_size(n), word_filled_by(bit)), sz(n) {}
template<typename It>
Bitmap(It begin, It end) : sz(0) {
using trait = std::iterator_traits<It>;
using iterator_category = typename trait::iterator_category;
static_assert(std::is_base_of<std::input_iterator_tag, iterator_category>::value, "");
static_assert(std::is_convertible<typename trait::value_type, bool>::value, "");
if constexpr (std::is_base_of<std::random_access_iterator_tag, iterator_category>::value) {
arr.reserve(required_word_size(std::distance(begin, end)));
}
for (auto it = begin; it != end; ++it)
push_back((bool)*it);
}
size_t size() const { return sz; }
bool empty() const { return size() == 0; }
void push_back(bool bit) {
auto r = sz % 64;
if (r == 0) {
arr.push_back((W)bit);
} else {
if (bit)
arr.back() |= 1ull << r;
else
arr.back() &= ~(1ull << r);
}
++sz;
}
void pop_back() {
--sz;
}
void resize(size_t new_size, bool bit=false) { // TODO: fix when bit = true
auto old_size = size();
sz = new_size;
if (new_size < old_size) {
return;
}
arr.resize(required_word_size(new_size), word_filled_by(bit));
auto r = old_size % 64;
if (r) {
W mask = (1ull << r) - 1;
if (bit)
arr[old_size / 64] |= ~mask;
else
arr[old_size / 64] &= mask;
}
}
void assign(size_t new_size, bool bit) {
sz = new_size;
arr.assign(required_word_size(new_size), word_filled_by(bit));
}
void reserve(size_t reserved_size) {
arr.reserve(required_word_size(reserved_size));
}
struct const_reference;
struct reference;
template<bool>
struct _iterator;
using const_iterator = _iterator<true>;
using iterator = _iterator<false>;
const_reference operator[](size_t i) const {
return const_reference(arr.data() + i / 64, 1ull << (i % 64));
}
reference operator[](size_t i) {
return {arr.data() + i / 64, 1ull << (i % 64)};
}
const_reference get(size_t i) const {
return operator[](i);
}
/**
* Usable without pre-set required size
*/
void set(size_t i, bool b) {
if (i >= size())
resize(i + 1);
operator[](i) = b;
}
/**
* No build process is needed
*/
void build() const {}
void move_or_build(Bitmap&& src) {
*this = std::move(src);
}
const_iterator begin() const { return const_iterator(arr.data(), 0); }
iterator begin() { return iterator(arr.data(), 0); }
const_iterator cbegin() const { return begin(); }
const_iterator end() const { return const_iterator(arr.data() + sz / 64, sz % 64); }
iterator end() { return iterator(arr.data() + sz / 64, sz % 64); }
const_iterator cend() const { return end(); }
template<bool Const>
struct reference_base {
using _pointer = typename std::conditional<Const, const W*, W*>::type;
using _iterator = typename std::conditional<Const, const_iterator, iterator>::type;
_pointer ptr;
W mask;
reference_base(_pointer ptr, W mask) : ptr(ptr), mask(mask) {}
reference_base(const reference_base&) = delete;
reference_base& operator=(const reference_base&) = delete;
reference_base(reference_base&&) noexcept = default;
reference_base& operator=(reference_base&&) noexcept = default;
inline operator bool() const {
return (*ptr & mask) != 0;
}
inline bool operator==(bool r) const {
return (bool) *this == r;
}
inline friend bool operator==(bool l, const reference_base& r) {
return r == l;
}
inline bool operator!=(bool r) const {
return (bool) *this != r;
}
inline friend bool operator!=(bool l, const reference_base& r) {
return r != l;
}
_iterator operator&() const {
return {ptr, bm::ctz(mask)};
}
std::ostream& operator<<(std::ostream& os) const {
return os << (bool) *this;
}
};
struct const_reference : public reference_base<true> {
using _base = reference_base<true>;
const_reference(_base::_pointer ptr, W mask) : _base(ptr, mask) {}
const_reference(const reference& rhs) : _base(rhs.ptr, rhs.mask) {}
};
struct reference : public reference_base<false> {
using _base = reference_base<false>;
reference(_base::_pointer ptr, W mask) : _base(ptr, mask) {}
inline reference& operator=(bool bit) {
if (bit)
*ptr |= mask;
else
*ptr &= ~mask;
return *this;
}
inline reference& operator|=(bool bit) {
if (bit)
*ptr |= mask;
return *this;
}
inline reference& operator&=(bool bit) {
if (!bit)
*ptr &= ~mask;
return *this;
}
template<bool C>
inline reference& operator=(const reference_base<C>& rhs) {
return *this = (bool) rhs;
}
reference(const reference& rhs) = delete;
reference(reference&& rhs) noexcept = default;
reference& operator=(reference&& rhs) noexcept = default;
std::istream& operator>>(std::istream& is) {
bool b;
is >> b;
operator=(b);
return is;
}
};
template<bool Const>
struct _iterator {
using iterator_category = std::random_access_iterator_tag;
using value_type = bool;
using difference_type = std::ptrdiff_t;
using pointer = iterator;
using reference = typename std::conditional<Const, const_reference, Bitmap::reference>::type;
using _pointer = typename std::conditional<Const, const W*, W*>::type;
_pointer ptr;
unsigned ctz;
_iterator(_pointer ptr, unsigned ctz) : ptr(ptr), ctz(ctz) {}
inline reference operator*() const {
return reference(ptr, 1ull << ctz);
}
template<bool C>
inline bool operator==(const _iterator<C>& r) const {
return ptr == r.ptr and ctz == r.ctz;
}
template<bool C>
inline bool operator!=(const _iterator<C>& r) const {
return ptr != r.ptr or ctz != r.ctz;
}
inline _iterator& operator++() {
if (ctz % 64 < 63) {
++ctz;
} else {
++ptr;
ctz = 0;
}
return *this;
}
inline _iterator operator++(int) {
_iterator ret = *this;
operator++();
return ret;
}
inline _iterator& operator--() {
if (ctz % 64 > 0) {
--ctz;
} else {
--ptr;
ctz = 63;
}
return *this;
}
inline _iterator operator--(int) {
_iterator ret = *this;
operator--();
return ret;
}
inline _iterator& operator+=(std::ptrdiff_t d) {
if (d < 0)
return operator-=(-d);
auto r = d % 64;
if (ctz + r < 64) {
ptr += d / 64;
ctz += r;
} else {
ptr += d / 64 + 1;
ctz = (ctz + r) - 64;
}
return *this;
}
inline _iterator operator+(std::ptrdiff_t d) const {
return _iterator(*this) += d;
}
inline _iterator& operator-=(std::ptrdiff_t d) {
if (d < 0)
return operator+=(-d);
auto r = d % 64;
if (r <= ctz) {
ptr -= d / 64;
ctz -= r;
} else {
ptr -= d / 64 + 1;
ctz = (ctz + 64 - r) - 64;
}
return *this;
}
inline _iterator operator-(std::ptrdiff_t d) const {
return _iterator(*this) -= d;
}
inline reference operator[](size_t i) const {
return *(*this + i);
}
};
void range_set(size_t b, size_t e, uint64_t x) {
if (b >= e) return;
auto r = b % 64;
auto w = e-b;
auto mask = w < 64 ? (1ull << w) - 1 : ~0ull;
assert(x <= mask);
arr[b/64] = (arr[b/64] & ~(mask << r)) | x << r;
if (mask + r > 64) {
arr[b/64+1] = (arr[b/64+1] & ~(mask >> (64-r))) | x >> (64-r);
}
}
uint64_t range_get(size_t b, size_t e) const {
if (b >= e) return 0;
assert(e-b <= 64);
auto r = b % 64;
auto w = e-b;
auto mask = w < 64 ? (1ull << w) - 1 : ~0ull;
auto x = arr[b/64] >> r;
if (w + r > 64)
x |= arr[b/64+1] << (64-r);
return x & mask;
}
const uint64_t& get_word(size_t wi) const {
return arr[wi];
}
size_t word_size() const {
return arr.size();
}
// using rank_select_type = BV<Bitmap, 64>;
};
#line 8 "include/mtl/succinct/ty.hpp"
/**
* @brief TY: Store increasing sequence of integers.
* Memory needs for store nth integers O(n log d) bits
* which d is max diff of consecutive elements.
*/
template<class T, class DiffType = int16_t>
class TY {
using value_type = T;
static constexpr auto block_size = sizeof(value_type) * 8;
using diff_value_type = DiffType;
static constexpr unsigned max_diff = std::numeric_limits<diff_value_type>::max();
private:
std::vector<value_type> head;
std::vector<diff_value_type> diff;
public:
TY() = default;
template<class It>
TY(It first, It last) {
assert(std::is_sorted(first, last));
reserve(std::distance(first, last));
for (auto it = first; it != last; it++) {
push_back(*it);
}
}
size_t size() const {
return head.size() + diff.size();
}
bool empty() const { return size() == 0; }
void reserve(size_t n) {
head.reserve((n + block_size - 1) / block_size);
diff.reserve(n / block_size * (block_size - 1) + n % block_size);
}
template<class... Args>
void emplace_back(Args&&... args) {
if (size() % block_size == 0) {
head.emplace_back(std::forward<Args>(args)...);
} else {
value_type v(std::forward<Args>(args)...);
assert(v >= head.back());
assert(v - head.back() <= (value_type)max_diff);
diff.push_back((diff_value_type)(v - head.back()));
}
}
void push_back(const value_type& v) {
if (size() % block_size == 0) {
head.push_back(v);
} else {
assert(v >= head.back());
assert(v - head.back() <= (value_type)max_diff);
diff.push_back(v - head.back());
}
}
void push_back(value_type&& v) {
emplace_back(std::move(v));
}
value_type get(size_t i) const {
if (i % block_size == 0)
return head[i / block_size];
else
return head[i / block_size] +
(value_type)diff[i / block_size * (block_size-1) + i % block_size - 1];
}
value_type operator[](size_t i) const { return get(i); }
value_type front() const { return get(0); }
value_type back() const { return get(size()-1); }
};
#line 7 "include/mtl/succinct/rrr.hpp"
#include <map>
#line 13 "include/mtl/succinct/rrr.hpp"
constexpr unsigned need_bits(uint64_t n) {
return bm::bit_width(n);
}
template<unsigned N>
struct BinomialTable {
static_assert(N < 64,
"Too large N for BinomialTable. N must be less than 64");
using number_type = uint64_t;
using binom_table_type = std::array<std::array<number_type, N+1>, N+1>;
static constexpr binom_table_type make_binomial_table() {
binom_table_type tb{};
tb[0][0] = 1;
for (size_t i = 1; i <= N; i++) {
tb[i][0] = tb[i-1][0];
for (size_t j = 1; j <= i; j++)
tb[i][j] = tb[i-1][j-1] + tb[i-1][j];
}
return tb;
}
static constexpr binom_table_type _binom_tb = make_binomial_table();
static constexpr number_type binom(size_t n, size_t k) {
assert(n <= N and k <= N);
return _binom_tb[n][k];
}
};
template<unsigned N>
constexpr typename BinomialTable<N>::binom_table_type BinomialTable<N>::_binom_tb;
template<class Def>
struct RRRTable {
using def = Def;
static constexpr unsigned s_size = def::s_size;
using s_type = typename def::s_type;
static constexpr unsigned n_bits = def::n_bits;
using binomial_table_type = BinomialTable<s_size>;
using number_type = typename binomial_table_type::number_type;
static constexpr s_type get_int(unsigned n, number_type k, unsigned bits = s_size) {
s_type res = 0;
const auto offset = bits;
s_type mask = ((s_type(1)<<bits)-1);
auto nn = n;
unsigned i = 0;
/*
Binary search time B = ceil(\log_2 w)
Expected length of consecutive zeros Ez = \sum j binom(w-j, nn) / binom(w, nn), j=1..w-nn
Expected length of consecutive ones Eo = \sum j binom(w-j, nn-j) / binom(w, nn), j=1..nn
Approximate simple function from Ez > B to be nn <= min(20, w-1)
Approximate simple function from Eo > B to be nn > min(40, w)
*/
// TODO: When nn > 40, use binary search to find length of consecutive ones
for (; i < offset and nn > 20; i++) {
auto w = s_size - i;
if (nn == w) {
res |= ((s_type(1)<<nn)-1) << i;
return res & mask;
}
if (nn == w-1) {
res |= (((s_type(1)<<w)-1) ^ (s_type(1) << k)) << i;
return res & mask;
}
// Linear search
auto binom = binomial_table_type::binom(w-1, nn);
if (k >= binom) {
res |= s_type(1) << i;
k -= binom;
nn--;
}
}
for (; i < offset and nn > 1; i++) {
auto w = s_size - i;
if (nn == w) {
res |= ((s_type(1)<<nn)-1) << i;
return res & mask;
}
if (nn == w-1) {
res |= (((s_type(1)<<w)-1) ^ (s_type(1) << k)) << i;
return res & mask;
}
// Binary search to find length of consecutive zeros
auto l = i, r = offset+1;
while (l+1<r) {
auto c = l+(r-l)/2;
if (k < binomial_table_type::binom(s_size-c, nn))
l = c;
else
r = c;
}
if (l < offset) {
res |= s_type(1) << l;
k -= binomial_table_type::binom(s_size-l-1, nn);
nn--;
}
i = l;
}
if (nn == 1) {
res |= s_type(1) << (s_size-1-k);
return res & mask;
}
if (nn == 0)
return res;
if (k >= binomial_table_type::binom(s_size-offset-1, nn))
res |= s_type(1) << offset;
return res & ((s_type(1)<<bits)-1);
}
static constexpr bool get_bit(unsigned n, number_type k, unsigned offset) {
auto nn = n;
unsigned i = 0;
/*
Binary search time B = ceil(\log_2 w)
Expected length of consecutive zeros Ez = \sum j binom(w-j, nn) / binom(w, nn), j=1..w-nn
Expected length of consecutive ones Eo = \sum j binom(w-j, nn-j) / binom(w, nn), j=1..nn
Approximate simple function from Ez > B to be nn <= min(20, w-1)
Approximate simple function from Eo > B to be nn > min(40, w)
*/
// TODO: When nn > 40, use binary search to find length of consecutive ones
for (; i < offset and nn > 20; i++) {
auto w = s_size - i;
if (nn == w) {
return 1;
}
if (nn == w-1) {
return offset != i+k;
}
// linear search
auto binom = binomial_table_type::binom(w-1, nn);
if (k >= binom) {
k -= binom;
nn--;
}
}
for (; i < offset and nn > 1; i++) {
auto w = s_size - i;
if (nn == w) {
return 1;
}
if (nn == w-1) {
return offset != i+k;
}
// binary search
auto l = i, r = offset+1;
while (l+1<r) {
auto c = l+(r-l)/2;
if (k < binomial_table_type::binom(s_size-c, nn))
l = c;
else
r = c;
}
if (l < offset) {
k -= binomial_table_type::binom(s_size-l-1, nn);
nn--;
}
i = l;
}
if (nn == 1)
return offset == s_size-1-k;
if (nn == 0)
return 0;
return k >= binomial_table_type::binom(s_size-offset-1, nn);
}
static constexpr number_type get_number_for_popcnt(s_type bitmap, unsigned pc) {
number_type number = 0;
auto m = bitmap;
auto n = pc;
while (m) {
auto i = bm::ctz(m);
number += binomial_table_type::binom(s_size-i-1, n);
n--;
m ^= (s_type(1)<<i);
}
return number;
}
static constexpr number_type number_size(unsigned n) {
return binomial_table_type::binom(s_size, n);
}
static constexpr std::pair<unsigned, number_type> get_pc_and_number(s_type bitmap) {
unsigned pc = bm::popcnt(bitmap);
auto number = pc <= s_size-pc ? get_number_for_popcnt(bitmap, pc)
: (number_size(pc)-1-get_number_for_popcnt(
~bitmap & ((s_type(1)<<s_size)-1), s_size-pc));
return std::make_pair(pc, number);
}
using number_bits_table_type = std::array<unsigned, s_size+1>;
static constexpr number_bits_table_type make_number_bits_table() {
number_bits_table_type tb{};
for (unsigned i = 0; i <= s_size; i++) {
tb[i] = need_bits(number_size(i)-1);
}
return tb;
}
static constexpr number_bits_table_type n_len = make_number_bits_table();
static constexpr unsigned number_bits(unsigned n) {
assert(n <= s_size);
return n_len[n];
}
};
template<class Def>
constexpr typename RRRTable<Def>::number_bits_table_type RRRTable<Def>::n_len;
template<unsigned SSize, class SType>
struct RRRDefinition {
static constexpr unsigned s_size = SSize;
using s_type = SType;
static constexpr unsigned n_bits = need_bits(s_size);
};
/**
* @brief Succinct bit vector in memory of B(n, u) + O(u log log n / log n) bits
* where u is number of bits and n is number of 1s
*/
template<
unsigned SSize = 63,
class SType = uint64_t,
class MapType = std::map<size_t, SType>
>
struct RRR {
using def = RRRDefinition<SSize, SType>;
using s_type = typename def::s_type;
using rrr_table_type = RRRTable<def>;
using map_type = MapType;
using ty_type = TY<size_t>;
map_type s_map;
ty_type heads;
Bitmap bm;
RRR() = default;
void set(size_t i, bool b) {
if (b)
s_map[i/def::s_size] |= (s_type)1<<(i%def::s_size);
else
s_map[i/def::s_size] &= ~((s_type)1<<(i%def::s_size));
}
void build() {
size_t h = 0;
size_t pq = 0;
auto block_count = s_map.empty() ? 0 : std::prev(s_map.end())->first+1;
heads.reserve(block_count);
for (auto qm : s_map) {
auto qidx = qm.first;
auto mask = qm.second;
while (pq < qidx) {
heads.push_back(h);
auto w = def::n_bits;
bm.resize(h+w);
bm.range_set(h, h+w, 0);
h += w;
pq++;
}
heads.push_back(h);
auto np = rrr_table_type::get_pc_and_number(mask);
auto n = np.first;
auto p = np.second;
assert(rrr_table_type::get_int(n, p) == mask);
auto w = def::n_bits + rrr_table_type::number_bits(n);
bm.resize(h+w);
bm.range_set(h, h+def::n_bits, n);
bm.range_set(h+def::n_bits, h+w, p);
assert(bm.range_get(h, h+def::n_bits) == n);
assert(bm.range_get(h+def::n_bits, h+w) == p);
h += w;
pq++;
}
s_map.clear();
}
void move_or_build(RRR&& src) {
*this = std::move(src);
}
void move_or_build(const Bitmap& bm) {
for (size_t i = 0; i < bm.size(); i += def::s_size) {
auto w = bm.range_get(i, std::min(i+def::s_size, bm.size()));
if (w or i+def::s_size >= bm.size()) s_map.emplace(i/def::s_size, w);
}
build();
}
bool get_bit(size_t si, unsigned off) const {
if (si >= heads.size())
return false;
auto a = heads.get(si);
auto b = a+def::n_bits;
auto n = bm.range_get(a, b);
auto p = bm.range_get(b, b+rrr_table_type::number_bits(n));
return rrr_table_type::get_bit(n, p, off);
}
s_type get_mask(size_t si) const {
if (si >= heads.size())
return 0;
auto a = heads.get(si);
auto b = a+def::n_bits;
auto n = bm.range_get(a, b);
auto p = bm.range_get(b, b+rrr_table_type::number_bits(n));
return rrr_table_type::get_int(n, p);
}
uint64_t get_word(size_t si) const {
return get_mask(si);
}
size_t word_size() const {
return heads.size();
}
size_t size() const {
return heads.size() * def::s_size;
}
bool empty() const {
return size() == 0;
}
bool get(size_t i) const {
return get_bit(i/def::s_size, i%def::s_size);
}
};
#line 5 "include/mtl/succinct/traits.hpp"
template<class T>
struct RankSelectTraits : std::false_type {};
template<>
struct RankSelectTraits<Bitmap> {
using rank_select_type = BV<Bitmap, 64>;
};
template<unsigned SSize, class SType, class MapType>
struct RankSelectTraits<RRR<SSize, SType, MapType>> {
using rank_select_type = BV<RRR<SSize, SType, MapType>, SSize>;
};
#line 10 "include/mtl/succinct/bit_vector.hpp"
struct BitVector {
using bitmap_type = Bitmap;
bitmap_type bm;
using rs_type = typename RankSelectTraits<bitmap_type>::rank_select_type;
rs_type rs_support;
// std::vector<uint64_t> _r, _s, _zs;
BitVector() = default;
explicit BitVector(size_t size) : bm(size) {}
BitVector(size_t size, bool bit) : bm(size, bit) {}
BitVector(const BitVector& rhs) : bm(rhs.bm), rs_support(rhs.rs_support) {
rs_support.set_ptr(&bm);
}
BitVector& operator=(const BitVector& rhs) {
bm = rhs.bm;
rs_support = rhs.rs_support;
rs_support.set_ptr(&bm);
return *this;
}
BitVector(BitVector&& rhs) noexcept :
bm(std::move(rhs.bm)),
rs_support(std::move(rhs.rs_support)) {
rs_support.set_ptr(&bm);
}
BitVector& operator=(BitVector&& rhs) noexcept {
bm = std::move(rhs.bm);
rs_support = std::move(rhs.rs_support);
rs_support.set_ptr(&bm);
return *this;
}
template<typename It>
BitVector(It begin, It end) : bm(begin, end) {
build();
}
size_t size() const { return bm.size(); }
bool empty() const { return bm.empty(); }
void push_back(bool bit) { bm.push_back(bit); }
void resize(size_t new_size, bool bit = false) { bm.resize(new_size, bit); }
void assign(size_t new_size, bool bit) { bm.assign(new_size, bit); }
void reserve(size_t reserved_size) { bm.reserve(reserved_size); }
bitmap_type& bitmap() { return bm; }
const bitmap_type& bitmap() const { return bm; }
bitmap_type::const_reference operator[](size_t i) const { return bm[i]; }
bitmap_type::reference operator[](size_t i) { return bm[i]; }
bitmap_type::const_iterator begin() const { return bm.begin(); }
bitmap_type::const_iterator end() const { return bm.end(); }
bitmap_type::iterator begin() { return bm.begin(); }
bitmap_type::iterator end() { return bm.end(); }
bitmap_type::const_iterator cbegin() const { return bm.cbegin(); }
bitmap_type::const_iterator cend() const { return bm.cend(); }
void build() {
rs_support.build(&bm);
}
inline size_t rank(size_t i) const {
return rs_support.rank1(i);
}
size_t rank1(size_t i) const {
return rs_support.rank1(i);
}
size_t rank0(size_t i) const {
return rs_support.rank0(i);
}
template<bool B>
size_t select(size_t n) const {
return rs_support.select<B>(n);
}
size_t select1(size_t n) const {
return rs_support.select<1>(n);
}
size_t select0(size_t n) const {
return rs_support.select<0>(n);
}
};
#line 10 "include/mtl/succinct/wavelet_tree.hpp"
template<typename T>
struct WaveletTree {
static constexpr unsigned H = 64 - bm::clz(std::numeric_limits<T>::max());
size_t n,h;
BitVector B;
WaveletTree() = default;
template<typename It>
WaveletTree(It begin, It end)
: n(std::distance(begin, end)), h(64 - bm::clz(*max_element(begin, end)))
{
using trait = std::iterator_traits<It>;
static_assert(std::is_base_of<std::input_iterator_tag, typename trait::iterator_category>::value, "");
static_assert(std::is_convertible<typename trait::value_type, T>::value, "");
assert(*min_element(begin, end) >= 0);
B.assign(h * n, false);
std::vector<T> S(begin, end);
std::vector<size_t> D = {0,n}, nd;
auto bit = B.begin();
std::queue<T> sz,so;
for (int k = h-1; k > 0; k--) {
for (size_t i = 0; i < n; i++, ++bit)
*bit = (S[i] & (1ull<<k)) != 0;
nd.clear();
nd.push_back(0);
for (size_t d = 0; d < D.size()-1; ++d) {
size_t l = D[d], r = D[d+1];
for (size_t i = l; i < r; ++i)
if ((S[i] & (1ull<<k)) == 0)
sz.push(S[i]);
else
so.push(S[i]);
int zs = sz.size();
{
auto i = l;
while (!sz.empty()) {
S[i++] = sz.front();
sz.pop();
}
while (!so.empty()) {
S[i++] = so.front();
so.pop();
}
assert(i == r);
}
if (zs)
nd.push_back(l + zs);
if (l + zs < r)
nd.push_back(r);
}
std::swap(D, nd);
}
for (size_t i = 0; i < n; i++, ++bit)
*bit = (S[i] & 1ull) != 0;
B.build();
}
std::pair<size_t,size_t> child(bool b, size_t l, size_t r) {
auto os = B.rank(r) - B.rank(l);
auto zs = r-l - os;
return !b ? std::make_pair(l + n, l + zs + n)
: std::make_pair(l + zs + n, r + n);
}
T get(size_t i) const {
size_t l = 0, r = n;
T ret = 0;
auto j = i;
for (int k = h-1; k > 0; k--) {
auto rl = B.rank(l),
rj = B.rank(l + j),
rr = B.rank(r);
auto zs = r - l - (rr - rl);
if (B[l + j]) {
ret |= 1ull<<k;
j = rj - rl;
l += n + zs;
r += n;
} else {
j = (l+j - rj) - (l - rl);
l += n;
r = l + zs;
}
}
if (B[l + j])
ret |= 1ull;
return ret;
}
size_t rank(T c, size_t i) const {
size_t l = 0, r = n;
auto j = i;
for (int k = h-1; k >= 0; k--) {
auto rl = B.rank(l), rj = B.rank(l + j), rr = B.rank(r);
auto zs = r - l - (rr - rl);
if (c & (1ull<<k)) {
j = rj - rl;
l += n + zs;
r += n;
} else {
j = (l+j - rj) - (l - rl);
l += n;
r = l + zs;
}
}
return j;
}
size_t rank_lower(T c, size_t i) const {
size_t l = 0, r = n;
auto j = i;
size_t ret = 0;
for (int k = h-1; k >= 0; k--) {
auto rl = B.rank(l), rj = B.rank(l+j), rr = B.rank(r);
auto zs = r - l - (rr - rl);
if (c & (1ull << k)) {
ret += (l+j - rj) - (l - rl);
j = rj - rl;
l += n + zs;
r += n;
} else {
j = (l+j - rj) - (l - rl);
l += n;
r = l + zs;
}
}
return ret;
}
std::tuple<size_t, size_t, size_t> rank_3way(T c, size_t i) const {
size_t lt = 0, gt = 0;
size_t l = 0, r = n, j = i;
for (int k = h-1; k >= 0; k--) {
auto rl = B.rank(l), rj = B.rank(l+j), rr = B.rank(r);
auto zs = r - l - (rr - rl);
if (c & (1ull << k)) {
lt += (l+j - rj) - (l - rl);
j = rj - rl;
l += n + zs;
r += n;
} else {
gt += rj - rl;
j = (l+j - rj) - (l - rl);
l += n;
r = l + zs;
}
}
return std::make_tuple(lt, j, gt);
}
std::array<int, H> ls;
size_t select(T c, size_t i) { // 0-indexed
size_t l = 0, r = n;
for (int k = h-1; k >= 0; k--) {
ls[k] = l;
auto rl = B.rank(l), rr = B.rank(r);
auto zs = r - l - (rr - rl);
if (c & (1ull<<k)) {
l += n + zs;
r += n;
} else {
l += n;
r = l + zs;
}
}
if (i >= r - l)
return n; // Not found
auto j = i;
for (int k = 0; k < (int)h; k++) {
auto rl = B.rank(ls[k]);
if (c & (1ull<<k)) {
r = rl;
j = B.select<1>(j + r) - ls[k];
} else {
r = ls[k] - rl;
j = B.select<0>(j + r) - ls[k];
}
}
return j;
}
private:
void _enumerate(size_t l, size_t r, size_t a, size_t b, T c,
std::vector<std::pair<T, size_t>>& enm) const {
if (b-a == 0)
return;
if (l >= n*h) {
enm.emplace_back(c, b-a);
return;
}
auto rl = B.rank(l),
rr = B.rank(r),
ra = B.rank(l+a) - rl,
rb = B.rank(l+b) - rl;
auto zs = (r - rr) - (l - rl);
_enumerate(l + n, l + n + zs, a - ra, b - rb, c, enm);
auto k = h-1 - l/n;
_enumerate(l + n + zs, r + n, ra, rb, c | (1ull << k), enm);
}
public:
std::vector<std::pair<T, size_t>> enumerate(size_t l, size_t r) const {
std::vector<std::pair<T, size_t>> enm;
_enumerate(0, n, l, r, T{0}, enm);
return enm;
}
private:
std::pair<size_t, size_t> child_tie(bool bit, size_t l, size_t r) const {
auto zs = (r-l) - (B.rank(r) - B.rank(l));
if (!bit)
return std::make_pair(l+n, l+n+zs);
else
return std::make_pair(l+n+zs, r+n);
}
public:
// Get frequency of values which (x <= value < y) in S[l,r).
size_t range_freq(size_t l, size_t r, T x, T y) const {
size_t freq = 0;
std::queue<std::tuple<size_t, size_t, T>> qs;
qs.emplace(l,r,0,n,T(0));
while (!qs.empty(0)) {
size_t i,j,_l,_r;
T c;
std::tie(i,j,_l,_r,c) = qs.front(); qs.pop();
if (i == j)
continue;
size_t level = i/n;
int shift = h-1-level;
T clo = c, chi = c | ((1ull<<(shift+1))-1);
if (chi < x or y <= clo)
continue;
if (x <= clo and chi < y) {
freq += j - i;
continue;
}
assert(level < h);
size_t rl = B.rank(_l), ri = B.rank(_l+i), rj = B.rank(_l+j), rr = B.rank(_r);
size_t zs = (_r - rr) - (_l - rl);
qs.emplace((_l+i - ri) - (_l - rl), (_l+j - rj) - (_l - rl),
_l+n, _l+n+zs, c);
qs.emplace(ri - rl, rj - rl,
_l+n+zs, _r+n, c|(1ull<<shift));
}
return freq;
}
};
#line 3 "test/succinct/wavelet_tree_test.cpp"
#include <bits/stdc++.h>
using namespace std;
int main() {
const int n = 1e6;
std::vector<char> S(n);
std::array<int, 26> cnt{};
std::array<std::vector<int>, 26> rank, select, rank_c;
for (int i = 0; i < 26; i++) {
rank[i].resize(n+1);
rank_c[i].resize(n+1);
}
for (int i = 0; i < n; i++) {
int c = rand()%26;
S[i] = c;
for (int j = 0; j < 26; j++) {
rank[j][i] = cnt[j];
if (j) rank_c[j][i] = rank_c[j-1][i] + cnt[j-1];
}
cnt[c]++;
select[c].push_back(i);
}
for (int i = 0; i < 26; i++) {
rank[i][n] = cnt[i];
if (i) rank_c[i][n] = rank_c[i-1][n] + cnt[i-1];
select[i].push_back(n);
}
WaveletTree<char> wm(S.begin(), S.end());
// access
for (int i = 0; i < n; i++) {
char v = wm.get(i);
if (v != S[i]) {
cout << "Failed access "<<i<<" wm.get: "<<char(v+'a')<<" != S: "<<char(S[i]+'a')<<endl;
return 1;
}
}
// rank
for (int i = 0; i <= n; i++) {
for (int c = 0; c < 26; c++) {
int v = wm.rank(c, i);
if (v != rank[c][i]) {
cout << "Failed rank "<<char(c+'a')<<", "<<i<<" wm.rank: "<<v<<" != rank: "<<rank[c][i]<<endl;
return 1;
}
}
}
// select
std::array<int, 26> selected{};
for (int i = 0; i < n; i++) {
int c = S[i];
int k = selected[c]++;
int v = wm.select(c, k);
if (v != select[c][k] or v != i) {
cout << "Failed select "<<char(S[i]+'a')<<", "<<k<<" wm.select: "<<v<<" != select: "<<select[c][k]<<endl;
return 1;
}
}
for (int c = 0; c < 26; c++) {
int k = selected[c];
int v = wm.select(c, k);
if (v != select[c][k] or v != n) {
cout << "Failed select "<<char(c + 'a')<<", "<<k<<" wm.select: "<<v<<" != select: "<<select[c][k]<<endl;
return 1;
}
}
// rank_c
for (int i = 0; i <= n; i++) {
for (int c = 0; c < 26; c++) {
int v = wm.rank_lower(c, i);
if (v != rank_c[c][i]) {
cout << "Failed rank_c "<<char(c+'a')<<", "<<i<<" wm.rank_lower: "<<v<<" != rank_c: "<<rank_c[c][i]<<endl;
return 1;
}
}
}
// enumerate
const int m = std::min(n, (int)cbrt(n*6));
for (int l = 0; l < m; l++) {
for (int r = l+1; r <= m; r++) {
std::array<int, 26> enm{};
for (int c = 0; c < 26; c++) enm[c] = rank[c][r] - rank[c][l];
auto _v = wm.enumerate(l, r);
std::array<int, 26> v{};
for (auto p : _v) v[p.first] = p.second;
for (int c = 0; c < 26; c++) {
if (v[c] != enm[c]) {
cout << "Failed enumerate "<<l<<", "<<r<<", "<<char(c+'a')<<" wm.enumerate: "<<v[c]<<" != "<<enm[c]<<endl;
return 1;
}
}
}
}
std::cout << "OK" << std::endl;
}