This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#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; }