cp-library-cpp
This documentation is automatically generated by online-judge-tools/verification-helper
Compressed Wavelet Matrix
(library/datastructure/compressed_wavelet_matrix.hpp)
- View this file on GitHub
- Last update: 2023-09-15 20:02:25+09:00
- Include:
#include "library/datastructure/compressed_wavelet_matrix.hpp"
Compressed Wavelet Matrix
Depends on
- Bit Vector
(library/datastructure/bit_vector.hpp)
- Wavelet Matrix
(library/datastructure/wavelet_matrix.hpp)
- Type Traits
(library/type_traits/type_traits.hpp)
- 座標圧縮
(library/util/coordinate_compressor.hpp)
Verified with
- test/src/datastructure/compressed_wavelet_matrix/range_kth_smallest.test.cpp
- test/src/datastructure/compressed_wavelet_matrix/static_range_frequency.test.cpp
- test/src/datastructure/compressed_wavelet_matrix/static_rmq.test.cpp
Code
#ifndef SUISEN_COMP_WAVELET_MATRIX
#define SUISEN_COMP_WAVELET_MATRIX
#include <cassert>
#include <array>
#include <type_traits>
#include <limits>
#include "library/datastructure/wavelet_matrix.hpp"
#include "library/util/coordinate_compressor.hpp"
namespace suisen {
template <typename T, int log_max_len = std::numeric_limits<std::make_unsigned_t<T>>::digits>
struct CompressedWaveletMatrix : private WaveletMatrix<int, log_max_len> {
// default constructor
CompressedWaveletMatrix() noexcept : WaveletMatrix<int, log_max_len>(0) {}
// builds WaveletMatrix from generating function typed as (int) -> T
template <typename Gen, constraints_t<std::is_invocable_r<T, Gen, int>> = nullptr>
CompressedWaveletMatrix(int n, Gen generator) : WaveletMatrix<int, log_max_len>(n), comp(CoordinateCompressorBuilder<T>::build(n, generator)) {
this->build([this, &generator](int i) { return comp[generator(i)]; });
}
// builds WaveletMatrix from vector
template <typename U, constraints_t<std::is_constructible<T, U>> = nullptr>
CompressedWaveletMatrix(const std::vector<U>& a) : CompressedWaveletMatrix(a.size(), [&a](int i) { return T(a[i]); }) {}
// returns WaveletMatrix[i]
inline T operator[](int i) const {
return comp.decomp(WaveletMatrix<int, log_max_len>::operator[](i));
}
// returns WaveletMatrix[i]
inline T access(int i) const {
return (*this)[i];
}
// returns the number of `val` in WaveletMatrix[0, i).
inline int rank(T val, int i) const {
int x = comp.comp(val, -1);
if (x == -1) return 0;
return WaveletMatrix<int, log_max_len>::rank(x, i);
}
// returns the k'th smallest value in WaveletMatrix[l, r) (k : 0-indexed)
inline T range_kth_smallest(int l, int r, int k, T default_value = T(-1)) const {
int x = WaveletMatrix<int, log_max_len>::range_kth_smallest(l, r, k, -1);
return x == -1 ? default_value : comp.decomp(x);
}
// returns the k'th largest value in WaveletMatrix[l, r) (k : 0-indexed)
inline T range_kth_largest(int l, int r, int k, T default_value = T(-1)) const {
int x = WaveletMatrix<int, log_max_len>::range_kth_largest(l, r, k, -1);
return x == -1 ? default_value : comp.decomp(x);
}
// returns the minimum value in WaveletMatrix[l, r)
inline T range_min(int l, int r) const {
return comp.decomp(WaveletMatrix<int, log_max_len>::range_min(l, r));
}
// returns the maximum value in WaveletMatrix[l, r)
inline T range_max(int l, int r) const {
return comp.decomp(WaveletMatrix<int, log_max_len>::range_max(l, r));
}
// returns the number of v in WaveletMatrix[l, r) s.t. v < upper
inline int range_freq(int l, int r, T upper) const {
return WaveletMatrix<int, log_max_len>::range_freq(l, r, comp.min_geq_index(upper));
}
// returns the number of v in WaveletMatrix[l, r) s.t. lower <= v < upper
inline int range_freq(int l, int r, T lower, T upper) const {
if (lower >= upper) return 0;
return range_freq(l, r, upper) - range_freq(l, r, lower);
}
// returns the minimum value v in WaveletMatrix[l, r) s.t. lower <= v
inline T range_min_geq(int l, int r, T lower, T default_value = T(-1)) const {
int x = WaveletMatrix<int, log_max_len>::range_min_geq(l, r, comp.min_geq_index(lower), -1);
return x == -1 ? default_value : comp.decomp(x);
}
// returns the minimum value v in WaveletMatrix[l, r) s.t. lower < v
inline T range_min_gt(int l, int r, T lower, T default_value = T(-1)) const {
return lower == std::numeric_limits<T>::max() ? default_value : range_min_geq(l, r, lower + 1, default_value);
}
// returns the maximum value v in WaveletMatrix[l, r) s.t. v < upper
inline T range_max_lt(int l, int r, T upper, T default_value = T(-1)) const {
int x = WaveletMatrix<int, log_max_len>::range_max_lt(l, r, comp.min_geq_index(upper), -1);
return x == -1 ? default_value : comp.decomp(x);
}
// returns the maximum value v in WaveletMatrix[l, r) s.t. v <= upper
inline T range_max_leq(int l, int r, T upper, T default_value = T(-1)) const {
if (r >= l) return default_value;
return upper == std::numeric_limits<T>::max() ? range_max(l, r) : range_max_lt(l, r, upper + 1, default_value);
}
private:
typename CoordinateCompressorBuilder<T>::Compressor comp;
};
} // namespace suisen
#endif // SUISEN_COMP_WAVELET_MATRIX#line 1 "library/datastructure/compressed_wavelet_matrix.hpp"
#include <cassert>
#include <array>
#include <type_traits>
#include <limits>
#line 1 "library/datastructure/wavelet_matrix.hpp"
#line 8 "library/datastructure/wavelet_matrix.hpp"
#line 1 "library/datastructure/bit_vector.hpp"
#include <cstdint>
#include <vector>
#line 1 "library/type_traits/type_traits.hpp"
#line 5 "library/type_traits/type_traits.hpp"
#include <iostream>
#line 7 "library/type_traits/type_traits.hpp"
namespace suisen {
template <typename ...Constraints> using constraints_t = std::enable_if_t<std::conjunction_v<Constraints...>, std::nullptr_t>;
template <typename T, typename = std::nullptr_t> struct bitnum { static constexpr int value = 0; };
template <typename T> struct bitnum<T, constraints_t<std::is_integral<T>>> { static constexpr int value = std::numeric_limits<std::make_unsigned_t<T>>::digits; };
template <typename T> static constexpr int bitnum_v = bitnum<T>::value;
template <typename T, size_t n> struct is_nbit { static constexpr bool value = bitnum_v<T> == n; };
template <typename T, size_t n> static constexpr bool is_nbit_v = is_nbit<T, n>::value;
template <typename T, typename = std::nullptr_t> struct safely_multipliable { using type = T; };
template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 32>>> { using type = long long; };
template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 64>>> { using type = __int128_t; };
template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 32>>> { using type = unsigned long long; };
template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 64>>> { using type = __uint128_t; };
template <typename T> using safely_multipliable_t = typename safely_multipliable<T>::type;
template <typename T, typename = void> struct rec_value_type { using type = T; };
template <typename T> struct rec_value_type<T, std::void_t<typename T::value_type>> {
using type = typename rec_value_type<typename T::value_type>::type;
};
template <typename T> using rec_value_type_t = typename rec_value_type<T>::type;
template <typename T> class is_iterable {
template <typename T_> static auto test(T_ e) -> decltype(e.begin(), e.end(), std::true_type{});
static std::false_type test(...);
public:
static constexpr bool value = decltype(test(std::declval<T>()))::value;
};
template <typename T> static constexpr bool is_iterable_v = is_iterable<T>::value;
template <typename T> class is_writable {
template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::ostream&>() << e, std::true_type{});
static std::false_type test(...);
public:
static constexpr bool value = decltype(test(std::declval<T>()))::value;
};
template <typename T> static constexpr bool is_writable_v = is_writable<T>::value;
template <typename T> class is_readable {
template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::istream&>() >> e, std::true_type{});
static std::false_type test(...);
public:
static constexpr bool value = decltype(test(std::declval<T>()))::value;
};
template <typename T> static constexpr bool is_readable_v = is_readable<T>::value;
} // namespace suisen
#line 8 "library/datastructure/bit_vector.hpp"
namespace suisen {
struct BitVector {
explicit BitVector(int n) : n(n), nl((n >> LOG_BLOCK_L) + 1), ns((n >> LOG_BLOCK_S) + 1), cum_l(nl, 0), cum_s(ns, 0), bits(ns, 0) {}
BitVector() : BitVector(0) {}
template <typename Gen, constraints_t<std::is_invocable_r<bool, Gen, int>> = nullptr>
BitVector(int n, Gen gen) : BitVector(n) {
build(gen);
}
BitVector& operator=(const BitVector& bv) {
n = bv.n, nl = bv.nl, ns = bv.ns, cum_l = bv.cum_l, cum_s = bv.cum_s, bits = bv.bits;
return *this;
}
BitVector& operator=(BitVector&& bv) {
n = bv.n, nl = bv.nl, ns = bv.ns, cum_l = std::move(bv.cum_l), cum_s = std::move(bv.cum_s), bits = std::move(bv.bits);
return *this;
}
template <typename Gen, constraints_t<std::is_invocable_r<bool, Gen, int>> = nullptr>
void build(Gen gen) {
int i = 0;
for (int index_s = 1; index_s < ns; ++index_s) {
int count = cum_s[index_s - 1];
for (; i < index_s << LOG_BLOCK_S; ++i) {
bool b = gen(i);
bits[index_s - 1] |= b << (i & MASK_S);
count += b;
}
if (index_s & ((1 << (LOG_BLOCK_L - LOG_BLOCK_S)) - 1)) {
cum_s[index_s] = count;
} else {
int index_l = i >> LOG_BLOCK_L;
cum_l[index_l] = cum_l[index_l - 1] + count;
}
}
for (; i < n; ++i) bits[ns - 1] |= gen(i) << (i & MASK_S);
}
bool operator[](int i) const {
return (bits[i >> LOG_BLOCK_S] >> (i & MASK_S)) & 1;
}
// returns the i'th val (i: 0-indexed)
bool access(int i) const {
return (*this)[i];
}
// returns the number of val in [0, i)
int rank(bool val, int i) const {
int res_1 = cum_l[i >> LOG_BLOCK_L] + cum_s[i >> LOG_BLOCK_S] + popcount8(bits[i >> LOG_BLOCK_S] & ((1 << (i & MASK_S)) - 1));
return val ? res_1 : i - res_1;
}
// returns the number of val in [l, r)
int rank(bool val, int l, int r) const {
return rank(val, r) - rank(val, l);
}
// find the index of num'th val. (num: 1-indexed). if not exists, returns default_value.
int select(bool val, int num, int default_value = -1) const {
int l = -1, r = n + 1;
while (r - l > 1) {
int m = (l + r) >> 1;
(rank(val, m) >= num ? r : l) = m;
}
return r == n + 1 ? default_value : r;
}
private:
static constexpr int LOG_BLOCK_L = 8;
static constexpr int LOG_BLOCK_S = 3;
static constexpr int MASK_S = (1 << LOG_BLOCK_S) - 1;
int n, nl, ns;
std::vector<int> cum_l;
std::vector<std::uint8_t> cum_s, bits;
static constexpr std::uint8_t popcount8(std::uint8_t x) {
x = (x & 0b01010101) + ((x >> 1) & 0b01010101);
x = (x & 0b00110011) + ((x >> 2) & 0b00110011);
return (x & 0b00001111) + (x >> 4);
}
};
} // namespace suisen
#line 10 "library/datastructure/wavelet_matrix.hpp"
namespace suisen {
template <typename T, int bit_num = std::numeric_limits<std::make_unsigned_t<T>>::digits>
struct WaveletMatrix {
// default constructor
WaveletMatrix() noexcept : n(0) {}
// builds WaveletMatrix from generating function typed as (int) -> T
template <typename Gen, constraints_t<std::is_invocable_r<T, Gen, int>> = nullptr>
WaveletMatrix(int n, Gen generator) : n(n) {
build(generator);
}
// builds WaveletMatrix from vector
template <typename U, constraints_t<std::is_constructible<T, U>> = nullptr>
WaveletMatrix(const std::vector<U>& a) : WaveletMatrix(a.size(), [&a](int i) { return T(a[i]); }) {}
// builds WaveletMatrix from generating function typed as (int) -> T
template <typename Gen, constraints_t<std::is_invocable_r<T, Gen, int>> = nullptr>
void build(Gen generator) {
std::vector<T> a(n), l(n), r(n);
for (int i = 0; i < n; ++i) a[i] = generator(i);
for (int log = bit_num - 1; log >= 0; --log) {
bv[log] = BitVector(n, [&a, log](int i) -> bool { return (a[i] >> log) & 1; });
int li = 0, ri = 0;
for (int i = 0; i < n; ++i) {
((a[i] >> log) & 1 ? r[ri++] : l[li++]) = a[i];
}
a.swap(l);
std::copy(r.begin(), r.begin() + ri, a.begin() + li);
mid[log] = li;
}
}
// returns WaveletMatrix[i]
T operator[](int i) const {
T res = 0;
for (int log = bit_num - 1; log >= 0; --log) {
bool b = bv[log][i];
res |= T(b) << log;
i = b * mid[log] + bv[log].rank(b, i);
}
return res;
}
// returns WaveletMatrix[i]
T access(int i) const {
return (*this)[i];
}
// returns the number of `val` in WaveletMatrix[0, i).
int rank(T val, int i) const {
check_value_bounds(val);
int l = 0, r = i;
for (int log = bit_num - 1; log >= 0; --log) succ(l, r, (val >> log) & 1, log);
return r - l;
}
// returns the k'th smallest value in the multiset {| x ^ WaveletMatrix[i] : i in [l, r) |} (k : 0-indexed)
T range_xor_kth_smallest(int l, int r, int k, T x, T default_value = T(-1)) const {
if (k < 0 or k >= r - l) return default_value;
T res = 0;
check_value_bounds(x);
for (int log = bit_num - 1; log >= 0; --log) {
bool z = (x >> log) & 1;
int cnt_z = bv[log].rank(z, l, r);
bool skip_z = k >= cnt_z, bit = z ^ skip_z;
succ(l, r, bit, log);
res |= T(bit) << log;
k -= skip_z * cnt_z;
}
return res;
}
// returns the k'th largest value in the multiset {| x ^ WaveletMatrix[i] : i in [l, r) |} (k : 0-indexed)
T range_xor_kth_largest(int l, int r, int k, T x, T default_value = T(-1)) const {
return range_xor_kth_smallest(l, r, r - l - 1 - k, x, default_value);
}
// returns the minimum value in the set { x ^ WaveletMatrix[i] : i in [l, r) }
T range_xor_min(int l, int r, T x) const {
assert(l < r);
return range_xor_kth_smallest(l, r, 0, x);
}
// returns the maximum value in the set { x ^ WaveletMatrix[i] : i in [l, r) }
T range_xor_max(int l, int r, T x) const {
assert(l < r);
return range_xor_kth_largest(l, r, 0, x);
}
// returns the number of v in WaveletMatrix[l, r) s.t. v ^ x < upper
int range_xor_freq(int l, int r, T x, T upper) const {
if (r <= l) return 0;
if (upper > MAX) return r - l;
check_value_bounds(x);
int res = 0;
for (int log = bit_num - 1; log >= 0; --log) {
bool z = (x >> log) & 1, u = (upper >> log) & 1;
if (u) res += bv[log].rank(z, l, r);
succ(l, r, z ^ u, log);
}
return res;
}
// returns the number of v in WaveletMatrix[l, r) s.t. lower <= x ^ v < upper
int range_xor_freq(int l, int r, T x, T lower, T upper) const {
if (lower >= upper) return 0;
return range_xor_freq(l, r, x, upper) - range_xor_freq(l, r, x, lower);
}
// returns the minimum value v in WaveletMatrix[l, r) s.t. lower <= x ^ v
T range_xor_min_geq(int l, int r, T x, T lower, T default_value = T(-1)) const {
int cnt = range_xor_freq(l, r, x, lower);
return cnt >= r - l ? default_value : range_xor_kth_smallest(l, r, cnt, x);
}
// returns the minimum value v in WaveletMatrix[l, r) s.t. lower < x ^ v
T range_xor_min_gt(int l, int r, T x, T lower, T default_value = T(-1)) const {
return lower == MAX ? default_value : range_xor_min_geq(l, r, x, lower + 1, default_value);
}
// returns the maximum value v in WaveletMatrix[l, r) s.t. x ^ v < upper
T range_xor_max_lt(int l, int r, T x, T upper, T default_value = T(-1)) const {
int cnt = range_xor_freq(l, r, x, upper);
return cnt == 0 ? default_value : range_xor_kth_smallest(l, r, cnt - 1, x, default_value);
}
// returns the maximum value v in WaveletMatrix[l, r) s.t. x ^ v <= upper
T range_xor_max_leq(int l, int r, T x, T upper, T default_value = T(-1)) const {
if (l >= r) return default_value;
return upper == MAX ? range_xor_max(l, r, x) : range_xor_max_lt(l, r, x, upper + 1, default_value);
}
// returns the k'th smallest value in WaveletMatrix[l, r) (k : 0-indexed)
T range_kth_smallest(int l, int r, int k, T default_value = T(-1)) const { return range_xor_kth_smallest(l, r, k, 0, default_value); }
// returns the k'th largest value in WaveletMatrix[l, r) (k : 0-indexed)
T range_kth_largest(int l, int r, int k, T default_value = T(-1)) const { return range_xor_kth_largest(l, r, k, 0, default_value); }
// returns the minimum value in WaveletMatrix[l, r)
T range_min(int l, int r) const { return range_xor_min(l, r, 0); }
// returns the maximum value in WaveletMatrix[l, r)
T range_max(int l, int r) const { return range_xor_max(l, r, 0); }
// returns the number of v in WaveletMatrix[l, r) s.t. v < upper
int range_freq(int l, int r, T upper) const { return range_xor_freq(l, r, 0, upper); }
// returns the number of v in WaveletMatrix[l, r) s.t. lower <= v < upper
int range_freq(int l, int r, T lower, T upper) const { return range_xor_freq(l, r, 0, lower, upper); }
// returns the minimum value v in WaveletMatrix[l, r) s.t. lower <= v
T range_min_geq(int l, int r, T lower, T default_value = T(-1)) const { return range_xor_min_geq(l, r, 0, lower, default_value); }
// returns the minimum value v in WaveletMatrix[l, r) s.t. lower < v
T range_min_gt(int l, int r, T lower, T default_value = T(-1)) const { return range_xor_min_gt(l, r, 0, lower, default_value); }
// returns the maximum value v in WaveletMatrix[l, r) s.t. v < upper
T range_max_lt(int l, int r, T upper, T default_value = T(-1)) const { return range_xor_max_lt(l, r, 0, upper, default_value); }
// returns the maximum value v in WaveletMatrix[l, r) s.t. v <= upper
T range_max_leq(int l, int r, T upper, T default_value = T(-1)) const { return range_xor_max_leq(l, r, 0, upper, default_value); }
protected:
WaveletMatrix(int n) noexcept : n(n) {}
private:
static_assert(bit_num > 0);
static constexpr T MAX = bit_num == std::numeric_limits<T>::digits ? std::numeric_limits<T>::max() : (T(1) << bit_num) - 1;
int n;
std::array<BitVector, bit_num> bv;
std::array<int, bit_num> mid;
void succ(int& l, int& r, const bool b, const int log) const {
l = b * mid[log] + bv[log].rank(b, l);
r = b * mid[log] + bv[log].rank(b, r);
}
static void check_value_bounds(T val) {
assert((val >> bit_num) == 0);
}
};
} // namespace suisen
#line 1 "library/util/coordinate_compressor.hpp"
#include <algorithm>
#line 7 "library/util/coordinate_compressor.hpp"
#line 9 "library/util/coordinate_compressor.hpp"
namespace suisen {
template <typename T>
class CoordinateCompressorBuilder {
public:
struct Compressor {
public:
static constexpr int absent = -1;
// default constructor
Compressor() : _xs(std::vector<T>{}) {}
// Construct from strictly sorted vector
Compressor(const std::vector<T> &xs) : _xs(xs) {
assert(is_strictly_sorted(xs));
}
// Return the number of distinct keys.
int size() const {
return _xs.size();
}
// Check if the element is registered.
bool has_key(const T &e) const {
return std::binary_search(_xs.begin(), _xs.end(), e);
}
// Compress the element. if not registered, returns `default_value`. (default: Compressor::absent)
int comp(const T &e, int default_value = absent) const {
const int res = min_geq_index(e);
return res != size() and _xs[res] == e ? res : default_value;
}
// Restore the element from the index.
T decomp(const int compressed_index) const {
return _xs[compressed_index];
}
// Compress the element. Equivalent to call `comp(e)`
int operator[](const T &e) const {
return comp(e);
}
// Return the minimum registered value greater than `e`. if not exists, return `default_value`.
T min_gt(const T &e, const T &default_value) const {
auto it = std::upper_bound(_xs.begin(), _xs.end(), e);
return it == _xs.end() ? default_value : *it;
}
// Return the minimum registered value greater than or equal to `e`. if not exists, return `default_value`.
T min_geq(const T &e, const T &default_value) const {
auto it = std::lower_bound(_xs.begin(), _xs.end(), e);
return it == _xs.end() ? default_value : *it;
}
// Return the maximum registered value less than `e`. if not exists, return `default_value`
T max_lt(const T &e, const T &default_value) const {
auto it = std::upper_bound(_xs.rbegin(), _xs.rend(), e, std::greater<T>());
return it == _xs.rend() ? default_value : *it;
}
// Return the maximum registered value less than or equal to `e`. if not exists, return `default_value`
T max_leq(const T &e, const T &default_value) const {
auto it = std::lower_bound(_xs.rbegin(), _xs.rend(), e, std::greater<T>());
return it == _xs.rend() ? default_value : *it;
}
// Return the compressed index of the minimum registered value greater than `e`. if not exists, return `compressor.size()`.
int min_gt_index(const T &e) const {
return std::upper_bound(_xs.begin(), _xs.end(), e) - _xs.begin();
}
// Return the compressed index of the minimum registered value greater than or equal to `e`. if not exists, return `compressor.size()`.
int min_geq_index(const T &e) const {
return std::lower_bound(_xs.begin(), _xs.end(), e) - _xs.begin();
}
// Return the compressed index of the maximum registered value less than `e`. if not exists, return -1.
int max_lt_index(const T &e) const {
return int(_xs.rend() - std::upper_bound(_xs.rbegin(), _xs.rend(), e, std::greater<T>())) - 1;
}
// Return the compressed index of the maximum registered value less than or equal to `e`. if not exists, return -1.
int max_leq_index(const T &e) const {
return int(_xs.rend() - std::lower_bound(_xs.rbegin(), _xs.rend(), e, std::greater<T>())) - 1;
}
private:
std::vector<T> _xs;
static bool is_strictly_sorted(const std::vector<T> &v) {
return std::adjacent_find(v.begin(), v.end(), std::greater_equal<T>()) == v.end();
}
};
CoordinateCompressorBuilder() : _xs(std::vector<T>{}) {}
explicit CoordinateCompressorBuilder(const std::vector<T> &xs) : _xs(xs) {}
explicit CoordinateCompressorBuilder(std::vector<T> &&xs) : _xs(std::move(xs)) {}
template <typename Gen, constraints_t<std::is_invocable_r<T, Gen, int>> = nullptr>
CoordinateCompressorBuilder(const int n, Gen generator) {
reserve(n);
for (int i = 0; i < n; ++i) push(generator(i));
}
// Attempt to preallocate enough memory for specified number of elements.
void reserve(int n) {
_xs.reserve(n);
}
// Add data.
void push(const T &first) {
_xs.push_back(first);
}
// Add data.
void push(T &&first) {
_xs.push_back(std::move(first));
}
// Add data in the range of [first, last).
template <typename Iterator>
auto push(const Iterator &first, const Iterator &last) -> decltype(std::vector<T>{}.push_back(*first), void()) {
for (auto it = first; it != last; ++it) _xs.push_back(*it);
}
// Add all data in the container. Equivalent to `push(iterable.begin(), iterable.end())`.
template <typename Iterable>
auto push(const Iterable &iterable) -> decltype(std::vector<T>{}.push_back(*iterable.begin()), void()) {
push(iterable.begin(), iterable.end());
}
// Add data.
template <typename ...Args>
void emplace(Args &&...args) {
_xs.emplace_back(std::forward<Args>(args)...);
}
// Build compressor.
auto build() {
std::sort(_xs.begin(), _xs.end()), _xs.erase(std::unique(_xs.begin(), _xs.end()), _xs.end());
return Compressor {_xs};
}
// Build compressor from vector.
static auto build(const std::vector<T> &xs) {
return CoordinateCompressorBuilder(xs).build();
}
// Build compressor from vector.
static auto build(std::vector<T> &&xs) {
return CoordinateCompressorBuilder(std::move(xs)).build();
}
// Build compressor from generator.
template <typename Gen, constraints_t<std::is_invocable_r<T, Gen, int>> = nullptr>
static auto build(const int n, Gen generator) {
return CoordinateCompressorBuilder<T>(n, generator).build();
}
private:
std::vector<T> _xs;
};
} // namespace suisen
#line 11 "library/datastructure/compressed_wavelet_matrix.hpp"
namespace suisen {
template <typename T, int log_max_len = std::numeric_limits<std::make_unsigned_t<T>>::digits>
struct CompressedWaveletMatrix : private WaveletMatrix<int, log_max_len> {
// default constructor
CompressedWaveletMatrix() noexcept : WaveletMatrix<int, log_max_len>(0) {}
// builds WaveletMatrix from generating function typed as (int) -> T
template <typename Gen, constraints_t<std::is_invocable_r<T, Gen, int>> = nullptr>
CompressedWaveletMatrix(int n, Gen generator) : WaveletMatrix<int, log_max_len>(n), comp(CoordinateCompressorBuilder<T>::build(n, generator)) {
this->build([this, &generator](int i) { return comp[generator(i)]; });
}
// builds WaveletMatrix from vector
template <typename U, constraints_t<std::is_constructible<T, U>> = nullptr>
CompressedWaveletMatrix(const std::vector<U>& a) : CompressedWaveletMatrix(a.size(), [&a](int i) { return T(a[i]); }) {}
// returns WaveletMatrix[i]
inline T operator[](int i) const {
return comp.decomp(WaveletMatrix<int, log_max_len>::operator[](i));
}
// returns WaveletMatrix[i]
inline T access(int i) const {
return (*this)[i];
}
// returns the number of `val` in WaveletMatrix[0, i).
inline int rank(T val, int i) const {
int x = comp.comp(val, -1);
if (x == -1) return 0;
return WaveletMatrix<int, log_max_len>::rank(x, i);
}
// returns the k'th smallest value in WaveletMatrix[l, r) (k : 0-indexed)
inline T range_kth_smallest(int l, int r, int k, T default_value = T(-1)) const {
int x = WaveletMatrix<int, log_max_len>::range_kth_smallest(l, r, k, -1);
return x == -1 ? default_value : comp.decomp(x);
}
// returns the k'th largest value in WaveletMatrix[l, r) (k : 0-indexed)
inline T range_kth_largest(int l, int r, int k, T default_value = T(-1)) const {
int x = WaveletMatrix<int, log_max_len>::range_kth_largest(l, r, k, -1);
return x == -1 ? default_value : comp.decomp(x);
}
// returns the minimum value in WaveletMatrix[l, r)
inline T range_min(int l, int r) const {
return comp.decomp(WaveletMatrix<int, log_max_len>::range_min(l, r));
}
// returns the maximum value in WaveletMatrix[l, r)
inline T range_max(int l, int r) const {
return comp.decomp(WaveletMatrix<int, log_max_len>::range_max(l, r));
}
// returns the number of v in WaveletMatrix[l, r) s.t. v < upper
inline int range_freq(int l, int r, T upper) const {
return WaveletMatrix<int, log_max_len>::range_freq(l, r, comp.min_geq_index(upper));
}
// returns the number of v in WaveletMatrix[l, r) s.t. lower <= v < upper
inline int range_freq(int l, int r, T lower, T upper) const {
if (lower >= upper) return 0;
return range_freq(l, r, upper) - range_freq(l, r, lower);
}
// returns the minimum value v in WaveletMatrix[l, r) s.t. lower <= v
inline T range_min_geq(int l, int r, T lower, T default_value = T(-1)) const {
int x = WaveletMatrix<int, log_max_len>::range_min_geq(l, r, comp.min_geq_index(lower), -1);
return x == -1 ? default_value : comp.decomp(x);
}
// returns the minimum value v in WaveletMatrix[l, r) s.t. lower < v
inline T range_min_gt(int l, int r, T lower, T default_value = T(-1)) const {
return lower == std::numeric_limits<T>::max() ? default_value : range_min_geq(l, r, lower + 1, default_value);
}
// returns the maximum value v in WaveletMatrix[l, r) s.t. v < upper
inline T range_max_lt(int l, int r, T upper, T default_value = T(-1)) const {
int x = WaveletMatrix<int, log_max_len>::range_max_lt(l, r, comp.min_geq_index(upper), -1);
return x == -1 ? default_value : comp.decomp(x);
}
// returns the maximum value v in WaveletMatrix[l, r) s.t. v <= upper
inline T range_max_leq(int l, int r, T upper, T default_value = T(-1)) const {
if (r >= l) return default_value;
return upper == std::numeric_limits<T>::max() ? range_max(l, r) : range_max_lt(l, r, upper + 1, default_value);
}
private:
typename CoordinateCompressorBuilder<T>::Compressor comp;
};
} // namespace suisen