cp-library-cpp
This documentation is automatically generated by online-judge-tools/verification-helper
test/src/datastructure/wavelet_matrix/dummy.test.cpp
- View this file on GitHub
- Last update: 2023-09-15 20:02:25+09:00
- Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A
Depends on
- Bit Vector
(library/datastructure/bit_vector.hpp)
- Wavelet Matrix
(library/datastructure/wavelet_matrix.hpp)
- Type Traits
(library/type_traits/type_traits.hpp)
Code
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <iostream>
#include <random>
#include "library/datastructure/wavelet_matrix.hpp"
template <typename T>
struct NaiveSolution {
NaiveSolution() = default;
NaiveSolution(std::vector<T> dat) : n(dat.size()), dat(dat) {}
T operator[](int i) const { return dat[i]; }
T access(int i) const { return (*this)[i]; }
int rank(T val, int i) const {
int res = 0;
for (int j = 0; j < i; ++j) res += dat[j] == val;
return res;
}
// returns the k'th smallest value in the multiset {| x ^ A[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;
std::vector<T> sorted;
for (int i = l; i < r; ++i) sorted.push_back(dat[i] ^ x);
std::sort(sorted.begin(), sorted.end());
return sorted[k] ^ x;
}
// returns the k'th largest value in the multiset {| x ^ A[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 {
if (k < 0 or k >= r - l) return default_value;
std::vector<T> sorted;
for (int i = l; i < r; ++i) sorted.push_back(dat[i] ^ x);
std::sort(sorted.begin(), sorted.end(), std::greater<T>());
return sorted[k] ^ x;
}
// returns the minimum value in the set { x ^ A[i] : i in [l, r) }
T range_xor_min(int l, int r, T x) const {
assert(l < r);
T min_val = std::numeric_limits<T>::max();
for (int i = l; i < r; ++i) min_val = std::min(min_val, dat[i] ^ x);
return min_val ^ x;
}
// returns the maximum value in the set { x ^ A[i] : i in [l, r) }
T range_xor_max(int l, int r, T x) const {
assert(l < r);
T max_val = std::numeric_limits<T>::min();
for (int i = l; i < r; ++i) max_val = std::max(max_val, dat[i] ^ x);
return max_val ^ x;
}
// returns the number of v in A[l, r) s.t. v ^ x < upper
int range_xor_freq(int l, int r, T x, T upper) const {
int res = 0;
for (int i = l; i < r; ++i) res += (dat[i] ^ x) < upper;
return res;
}
// returns the number of v in A[l, r) s.t. lower <= x ^ v < upper
int range_xor_freq(int l, int r, T x, T lower, T upper) const {
int res = 0;
for (int i = l; i < r; ++i) res += lower <= (dat[i] ^ x) and (dat[i] ^ x) < upper;
return res;
}
// returns the minimum value v in A[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 {
bool upd = false;
T min_val = std::numeric_limits<T>::max();
for (int i = l; i < r; ++i) if (T v = dat[i] ^ x; lower <= v and v <= min_val) min_val = v, upd = true;
return upd ? min_val ^ x : default_value;
}
// returns the minimum value v in A[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 {
bool upd = false;
T min_val = std::numeric_limits<T>::max();
for (int i = l; i < r; ++i) if (T v = dat[i] ^ x; lower < v and v <= min_val) min_val = v, upd = true;
return upd ? min_val ^ x : default_value;
}
// returns the maximum value v in A[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 {
bool upd = false;
T max_val = std::numeric_limits<T>::min();
for (int i = l; i < r; ++i) if (T v = dat[i] ^ x; v < upper and max_val <= v) max_val = v, upd = true;
return upd ? max_val ^ x : default_value;
}
// returns the maximum value v in A[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 {
bool upd = false;
T max_val = std::numeric_limits<T>::min();
for (int i = l; i < r; ++i) if (T v = dat[i] ^ x; v <= upper and max_val <= v) max_val = v, upd = true;
return upd ? max_val ^ x : default_value;
}
// returns the k'th smallest value in A[l, r) (k : 0-indexed)
T range_kth_smallest(int l, int r, int k, T default_value = T(-1)) const {
if (k < 0 or k >= r - l) return default_value;
std::vector<T> sorted;
for (int i = l; i < r; ++i) sorted.push_back(dat[i]);
std::sort(sorted.begin(), sorted.end());
return sorted[k];
}
// returns the k'th largest value in A[l, r) (k : 0-indexed)
T range_kth_largest(int l, int r, int k, T default_value = T(-1)) const {
if (k < 0 or k >= r - l) return default_value;
std::vector<T> sorted;
for (int i = l; i < r; ++i) sorted.push_back(dat[i]);
std::sort(sorted.begin(), sorted.end(), std::greater<T>());
return sorted[k];
}
// returns the minimum value in A[l, r)
T range_min(int l, int r) const {
assert(l < r);
T min_val = std::numeric_limits<T>::max();
for (int i = l; i < r; ++i) min_val = std::min(min_val, dat[i]);
return min_val;
}
// returns the maximum value in A[l, r)
T range_max(int l, int r) const {
assert(l < r);
T max_val = std::numeric_limits<T>::min();
for (int i = l; i < r; ++i) max_val = std::max(max_val, dat[i]);
return max_val;
}
// returns the number of v in A[l, r) s.t. v < upper
int range_freq(int l, int r, T upper) const {
int res = 0;
for (int i = l; i < r; ++i) res += (dat[i]) < upper;
return res;
}
// returns the number of v in A[l, r) s.t. lower <= v < upper
int range_freq(int l, int r, T lower, T upper) const {
int res = 0;
for (int i = l; i < r; ++i) res += lower <= (dat[i]) and (dat[i]) < upper;
return res;
}
// returns the minimum value v in A[l, r) s.t. lower <= v
T range_min_geq(int l, int r, T lower, T default_value = T(-1)) const {
bool upd = false;
T min_val = std::numeric_limits<T>::max();
for (int i = l; i < r; ++i) if (T v = dat[i]; lower <= v and v <= min_val) min_val = v, upd = true;
return upd ? min_val : default_value;
}
// returns the minimum value v in A[l, r) s.t. lower < v
T range_min_gt(int l, int r, T lower, T default_value = T(-1)) const {
bool upd = false;
T min_val = std::numeric_limits<T>::max();
for (int i = l; i < r; ++i) if (T v = dat[i]; lower < v and v <= min_val) min_val = v, upd = true;
return upd ? min_val : default_value;
}
// returns the maximum value v in A[l, r) s.t. v < upper
T range_max_lt(int l, int r, T upper, T default_value = T(-1)) const {
bool upd = false;
T max_val = std::numeric_limits<T>::min();
for (int i = l; i < r; ++i) if (T v = dat[i]; v < upper and max_val <= v) max_val = v, upd = true;
return upd ? max_val : default_value;
}
// returns the maximum value v in A[l, r) s.t. v <= upper
T range_max_leq(int l, int r, T upper, T default_value = T(-1)) const {
bool upd = false;
T max_val = std::numeric_limits<T>::min();
for (int i = l; i < r; ++i) if (T v = dat[i]; v <= upper and max_val <= v) max_val = v, upd = true;
return upd ? max_val : default_value;
}
private:
int n;
std::vector<T> dat;
};
using suisen::WaveletMatrix;
// std::mt19937 rng{std::random_device{}()};
std::mt19937 rng{0};
template <typename T, int bit_num>
void test(int n, int q) {
std::uniform_int_distribution<T> value_dist(0, (T(1) << bit_num) - 1);
std::vector<T> dat(n);
for (auto &e : dat) e = value_dist(rng);
WaveletMatrix<T, bit_num> wm(dat);
NaiveSolution<T> naive(dat);
std::uniform_int_distribution<int> query_dist(0, 21);
std::uniform_int_distribution<int> index_dist(0, n - 1);
std::uniform_int_distribution<int> range_dist(0, n);
auto query = [&]{
return query_dist(rng);
};
auto index = [&]{
return index_dist(rng);
};
auto index_n = [&] {
return range_dist(rng);
};
auto range = [&]{
int l = index_n();
int r = index_n();
if (l > r) std::swap(l, r);
return std::make_pair(l, r);
};
auto nonempty_range = [&] {
int l, r;
do {
std::tie(l, r) = range();
} while (l >= r);
return std::make_pair(l, r);
};
auto value = [&] {
return value_dist(rng);
};
auto value_range = [&]{
T l = value();
T r = value();
if (l > r) std::swap(l, r);
return std::make_pair(l, r);
};
while (q --> 0) {
int qt = query();
if (qt == 0) {
int i = index();
assert(naive.access(i) == wm.access(i));
} else if (qt == 1) {
T v = value();
int i = index_n();
assert(naive.rank(v, i) == wm.rank(v, i));
} else if (qt == 2) {
auto [l, r] = range();
int k = rng() % (r - l + 1) + l;
T x = value();
assert(naive.range_xor_kth_smallest(l, r, k, x) == wm.range_xor_kth_smallest(l, r, k, x));
} else if (qt == 3) {
auto [l, r] = range();
int k = rng() % (r - l + 1) + l;
T x = value();
assert(naive.range_xor_kth_largest(l, r, k, x) == wm.range_xor_kth_largest(l, r, k, x));
} else if (qt == 4) {
auto [l, r] = nonempty_range();
T x = value();
assert(naive.range_xor_min(l, r, x) == wm.range_xor_min(l, r, x));
} else if (qt == 5) {
auto [l, r] = nonempty_range();
T x = value();
assert(naive.range_xor_max(l, r, x) == wm.range_xor_max(l, r, x));
} else if (qt == 6) {
auto [l, r] = range();
T x = value();
T upper = value();
assert(naive.range_xor_freq(l, r, x, upper) == wm.range_xor_freq(l, r, x, upper));
} else if (qt == 7) {
auto [l, r] = range();
T x = value();
auto [lower, upper] = value_range();
assert(naive.range_xor_freq(l, r, x, lower, upper) == wm.range_xor_freq(l, r, x, lower, upper));
} else if (qt == 8) {
auto [l, r] = range();
T x = value();
T v = value();
assert(naive.range_xor_min_geq(l, r, x, v) == wm.range_xor_min_geq(l, r, x, v));
} else if (qt == 9) {
auto [l, r] = range();
T x = value();
T v = value();
assert(naive.range_xor_min_gt(l, r, x, v) == wm.range_xor_min_gt(l, r, x, v));
} else if (qt == 10) {
auto [l, r] = range();
T x = value();
T v = value();
assert(naive.range_xor_max_lt(l, r, x, v) == wm.range_xor_max_lt(l, r, x, v));
} else if (qt == 11) {
auto [l, r] = range();
T x = value();
T v = value();
assert(naive.range_xor_max_leq(l, r, x, v) == wm.range_xor_max_leq(l, r, x, v));
} else if (qt == 12) {
auto [l, r] = range();
int k = rng() % (r - l + 1) + l;
assert(naive.range_kth_smallest(l, r, k) == wm.range_kth_smallest(l, r, k));
} else if (qt == 13) {
auto [l, r] = range();
int k = rng() % (r - l + 1) + l;
assert(naive.range_kth_largest(l, r, k) == wm.range_kth_largest(l, r, k));
} else if (qt == 14) {
auto [l, r] = nonempty_range();
assert(naive.range_min(l, r) == wm.range_min(l, r));
} else if (qt == 15) {
auto [l, r] = nonempty_range();
assert(naive.range_max(l, r) == wm.range_max(l, r));
} else if (qt == 16) {
auto [l, r] = range();
T upper = value();
assert(naive.range_freq(l, r, upper) == wm.range_freq(l, r, upper));
} else if (qt == 17) {
auto [l, r] = range();
auto [lower, upper] = value_range();
assert(naive.range_freq(l, r, lower, upper) == wm.range_freq(l, r, lower, upper));
} else if (qt == 18) {
auto [l, r] = range();
T v = value();
assert(naive.range_min_geq(l, r, v) == wm.range_min_geq(l, r, v));
} else if (qt == 19) {
auto [l, r] = range();
T v = value();
assert(naive.range_min_gt(l, r, v) == wm.range_min_gt(l, r, v));
} else if (qt == 20) {
auto [l, r] = range();
T v = value();
assert(naive.range_max_lt(l, r, v) == wm.range_max_lt(l, r, v));
} else if (qt == 21) {
auto [l, r] = range();
T v = value();
assert(naive.range_max_leq(l, r, v) == wm.range_max_leq(l, r, v));
}
}
std::cerr << "done" << std::endl;
}
void tests() {
test<int, 1>(100, 1000);
test<int, 2>(100, 1000);
test<int, 5>(100, 1000);
test<int, 7>(100, 100000);
test<int, 16>(100, 100000);
test<int, 30>(100, 100000);
test<long long, 16>(100, 100000);
test<long long, 62>(100, 100000);
test<int, 16>(1, 100);
test<long long, 16>(1, 100);
}
int main() {
tests();
std::cout << "Hello World" << std::endl;
return 0;
}#line 1 "test/src/datastructure/wavelet_matrix/dummy.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <iostream>
#include <random>
#line 1 "library/datastructure/wavelet_matrix.hpp"
#include <cassert>
#include <array>
#include <type_traits>
#include <limits>
#line 1 "library/datastructure/bit_vector.hpp"
#include <cstdint>
#include <vector>
#line 1 "library/type_traits/type_traits.hpp"
#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 8 "test/src/datastructure/wavelet_matrix/dummy.test.cpp"
template <typename T>
struct NaiveSolution {
NaiveSolution() = default;
NaiveSolution(std::vector<T> dat) : n(dat.size()), dat(dat) {}
T operator[](int i) const { return dat[i]; }
T access(int i) const { return (*this)[i]; }
int rank(T val, int i) const {
int res = 0;
for (int j = 0; j < i; ++j) res += dat[j] == val;
return res;
}
// returns the k'th smallest value in the multiset {| x ^ A[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;
std::vector<T> sorted;
for (int i = l; i < r; ++i) sorted.push_back(dat[i] ^ x);
std::sort(sorted.begin(), sorted.end());
return sorted[k] ^ x;
}
// returns the k'th largest value in the multiset {| x ^ A[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 {
if (k < 0 or k >= r - l) return default_value;
std::vector<T> sorted;
for (int i = l; i < r; ++i) sorted.push_back(dat[i] ^ x);
std::sort(sorted.begin(), sorted.end(), std::greater<T>());
return sorted[k] ^ x;
}
// returns the minimum value in the set { x ^ A[i] : i in [l, r) }
T range_xor_min(int l, int r, T x) const {
assert(l < r);
T min_val = std::numeric_limits<T>::max();
for (int i = l; i < r; ++i) min_val = std::min(min_val, dat[i] ^ x);
return min_val ^ x;
}
// returns the maximum value in the set { x ^ A[i] : i in [l, r) }
T range_xor_max(int l, int r, T x) const {
assert(l < r);
T max_val = std::numeric_limits<T>::min();
for (int i = l; i < r; ++i) max_val = std::max(max_val, dat[i] ^ x);
return max_val ^ x;
}
// returns the number of v in A[l, r) s.t. v ^ x < upper
int range_xor_freq(int l, int r, T x, T upper) const {
int res = 0;
for (int i = l; i < r; ++i) res += (dat[i] ^ x) < upper;
return res;
}
// returns the number of v in A[l, r) s.t. lower <= x ^ v < upper
int range_xor_freq(int l, int r, T x, T lower, T upper) const {
int res = 0;
for (int i = l; i < r; ++i) res += lower <= (dat[i] ^ x) and (dat[i] ^ x) < upper;
return res;
}
// returns the minimum value v in A[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 {
bool upd = false;
T min_val = std::numeric_limits<T>::max();
for (int i = l; i < r; ++i) if (T v = dat[i] ^ x; lower <= v and v <= min_val) min_val = v, upd = true;
return upd ? min_val ^ x : default_value;
}
// returns the minimum value v in A[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 {
bool upd = false;
T min_val = std::numeric_limits<T>::max();
for (int i = l; i < r; ++i) if (T v = dat[i] ^ x; lower < v and v <= min_val) min_val = v, upd = true;
return upd ? min_val ^ x : default_value;
}
// returns the maximum value v in A[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 {
bool upd = false;
T max_val = std::numeric_limits<T>::min();
for (int i = l; i < r; ++i) if (T v = dat[i] ^ x; v < upper and max_val <= v) max_val = v, upd = true;
return upd ? max_val ^ x : default_value;
}
// returns the maximum value v in A[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 {
bool upd = false;
T max_val = std::numeric_limits<T>::min();
for (int i = l; i < r; ++i) if (T v = dat[i] ^ x; v <= upper and max_val <= v) max_val = v, upd = true;
return upd ? max_val ^ x : default_value;
}
// returns the k'th smallest value in A[l, r) (k : 0-indexed)
T range_kth_smallest(int l, int r, int k, T default_value = T(-1)) const {
if (k < 0 or k >= r - l) return default_value;
std::vector<T> sorted;
for (int i = l; i < r; ++i) sorted.push_back(dat[i]);
std::sort(sorted.begin(), sorted.end());
return sorted[k];
}
// returns the k'th largest value in A[l, r) (k : 0-indexed)
T range_kth_largest(int l, int r, int k, T default_value = T(-1)) const {
if (k < 0 or k >= r - l) return default_value;
std::vector<T> sorted;
for (int i = l; i < r; ++i) sorted.push_back(dat[i]);
std::sort(sorted.begin(), sorted.end(), std::greater<T>());
return sorted[k];
}
// returns the minimum value in A[l, r)
T range_min(int l, int r) const {
assert(l < r);
T min_val = std::numeric_limits<T>::max();
for (int i = l; i < r; ++i) min_val = std::min(min_val, dat[i]);
return min_val;
}
// returns the maximum value in A[l, r)
T range_max(int l, int r) const {
assert(l < r);
T max_val = std::numeric_limits<T>::min();
for (int i = l; i < r; ++i) max_val = std::max(max_val, dat[i]);
return max_val;
}
// returns the number of v in A[l, r) s.t. v < upper
int range_freq(int l, int r, T upper) const {
int res = 0;
for (int i = l; i < r; ++i) res += (dat[i]) < upper;
return res;
}
// returns the number of v in A[l, r) s.t. lower <= v < upper
int range_freq(int l, int r, T lower, T upper) const {
int res = 0;
for (int i = l; i < r; ++i) res += lower <= (dat[i]) and (dat[i]) < upper;
return res;
}
// returns the minimum value v in A[l, r) s.t. lower <= v
T range_min_geq(int l, int r, T lower, T default_value = T(-1)) const {
bool upd = false;
T min_val = std::numeric_limits<T>::max();
for (int i = l; i < r; ++i) if (T v = dat[i]; lower <= v and v <= min_val) min_val = v, upd = true;
return upd ? min_val : default_value;
}
// returns the minimum value v in A[l, r) s.t. lower < v
T range_min_gt(int l, int r, T lower, T default_value = T(-1)) const {
bool upd = false;
T min_val = std::numeric_limits<T>::max();
for (int i = l; i < r; ++i) if (T v = dat[i]; lower < v and v <= min_val) min_val = v, upd = true;
return upd ? min_val : default_value;
}
// returns the maximum value v in A[l, r) s.t. v < upper
T range_max_lt(int l, int r, T upper, T default_value = T(-1)) const {
bool upd = false;
T max_val = std::numeric_limits<T>::min();
for (int i = l; i < r; ++i) if (T v = dat[i]; v < upper and max_val <= v) max_val = v, upd = true;
return upd ? max_val : default_value;
}
// returns the maximum value v in A[l, r) s.t. v <= upper
T range_max_leq(int l, int r, T upper, T default_value = T(-1)) const {
bool upd = false;
T max_val = std::numeric_limits<T>::min();
for (int i = l; i < r; ++i) if (T v = dat[i]; v <= upper and max_val <= v) max_val = v, upd = true;
return upd ? max_val : default_value;
}
private:
int n;
std::vector<T> dat;
};
using suisen::WaveletMatrix;
// std::mt19937 rng{std::random_device{}()};
std::mt19937 rng{0};
template <typename T, int bit_num>
void test(int n, int q) {
std::uniform_int_distribution<T> value_dist(0, (T(1) << bit_num) - 1);
std::vector<T> dat(n);
for (auto &e : dat) e = value_dist(rng);
WaveletMatrix<T, bit_num> wm(dat);
NaiveSolution<T> naive(dat);
std::uniform_int_distribution<int> query_dist(0, 21);
std::uniform_int_distribution<int> index_dist(0, n - 1);
std::uniform_int_distribution<int> range_dist(0, n);
auto query = [&]{
return query_dist(rng);
};
auto index = [&]{
return index_dist(rng);
};
auto index_n = [&] {
return range_dist(rng);
};
auto range = [&]{
int l = index_n();
int r = index_n();
if (l > r) std::swap(l, r);
return std::make_pair(l, r);
};
auto nonempty_range = [&] {
int l, r;
do {
std::tie(l, r) = range();
} while (l >= r);
return std::make_pair(l, r);
};
auto value = [&] {
return value_dist(rng);
};
auto value_range = [&]{
T l = value();
T r = value();
if (l > r) std::swap(l, r);
return std::make_pair(l, r);
};
while (q --> 0) {
int qt = query();
if (qt == 0) {
int i = index();
assert(naive.access(i) == wm.access(i));
} else if (qt == 1) {
T v = value();
int i = index_n();
assert(naive.rank(v, i) == wm.rank(v, i));
} else if (qt == 2) {
auto [l, r] = range();
int k = rng() % (r - l + 1) + l;
T x = value();
assert(naive.range_xor_kth_smallest(l, r, k, x) == wm.range_xor_kth_smallest(l, r, k, x));
} else if (qt == 3) {
auto [l, r] = range();
int k = rng() % (r - l + 1) + l;
T x = value();
assert(naive.range_xor_kth_largest(l, r, k, x) == wm.range_xor_kth_largest(l, r, k, x));
} else if (qt == 4) {
auto [l, r] = nonempty_range();
T x = value();
assert(naive.range_xor_min(l, r, x) == wm.range_xor_min(l, r, x));
} else if (qt == 5) {
auto [l, r] = nonempty_range();
T x = value();
assert(naive.range_xor_max(l, r, x) == wm.range_xor_max(l, r, x));
} else if (qt == 6) {
auto [l, r] = range();
T x = value();
T upper = value();
assert(naive.range_xor_freq(l, r, x, upper) == wm.range_xor_freq(l, r, x, upper));
} else if (qt == 7) {
auto [l, r] = range();
T x = value();
auto [lower, upper] = value_range();
assert(naive.range_xor_freq(l, r, x, lower, upper) == wm.range_xor_freq(l, r, x, lower, upper));
} else if (qt == 8) {
auto [l, r] = range();
T x = value();
T v = value();
assert(naive.range_xor_min_geq(l, r, x, v) == wm.range_xor_min_geq(l, r, x, v));
} else if (qt == 9) {
auto [l, r] = range();
T x = value();
T v = value();
assert(naive.range_xor_min_gt(l, r, x, v) == wm.range_xor_min_gt(l, r, x, v));
} else if (qt == 10) {
auto [l, r] = range();
T x = value();
T v = value();
assert(naive.range_xor_max_lt(l, r, x, v) == wm.range_xor_max_lt(l, r, x, v));
} else if (qt == 11) {
auto [l, r] = range();
T x = value();
T v = value();
assert(naive.range_xor_max_leq(l, r, x, v) == wm.range_xor_max_leq(l, r, x, v));
} else if (qt == 12) {
auto [l, r] = range();
int k = rng() % (r - l + 1) + l;
assert(naive.range_kth_smallest(l, r, k) == wm.range_kth_smallest(l, r, k));
} else if (qt == 13) {
auto [l, r] = range();
int k = rng() % (r - l + 1) + l;
assert(naive.range_kth_largest(l, r, k) == wm.range_kth_largest(l, r, k));
} else if (qt == 14) {
auto [l, r] = nonempty_range();
assert(naive.range_min(l, r) == wm.range_min(l, r));
} else if (qt == 15) {
auto [l, r] = nonempty_range();
assert(naive.range_max(l, r) == wm.range_max(l, r));
} else if (qt == 16) {
auto [l, r] = range();
T upper = value();
assert(naive.range_freq(l, r, upper) == wm.range_freq(l, r, upper));
} else if (qt == 17) {
auto [l, r] = range();
auto [lower, upper] = value_range();
assert(naive.range_freq(l, r, lower, upper) == wm.range_freq(l, r, lower, upper));
} else if (qt == 18) {
auto [l, r] = range();
T v = value();
assert(naive.range_min_geq(l, r, v) == wm.range_min_geq(l, r, v));
} else if (qt == 19) {
auto [l, r] = range();
T v = value();
assert(naive.range_min_gt(l, r, v) == wm.range_min_gt(l, r, v));
} else if (qt == 20) {
auto [l, r] = range();
T v = value();
assert(naive.range_max_lt(l, r, v) == wm.range_max_lt(l, r, v));
} else if (qt == 21) {
auto [l, r] = range();
T v = value();
assert(naive.range_max_leq(l, r, v) == wm.range_max_leq(l, r, v));
}
}
std::cerr << "done" << std::endl;
}
void tests() {
test<int, 1>(100, 1000);
test<int, 2>(100, 1000);
test<int, 5>(100, 1000);
test<int, 7>(100, 100000);
test<int, 16>(100, 100000);
test<int, 30>(100, 100000);
test<long long, 16>(100, 100000);
test<long long, 62>(100, 100000);
test<int, 16>(1, 100);
test<long long, 16>(1, 100);
}
int main() {
tests();
std::cout << "Hello World" << std::endl;
return 0;
}