This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#include "library/range_query/static_range_xored_mex_query.hpp"
#ifndef SUISEN_RANGE_XORED_MEX_QUERY #define SUISEN_RANGE_XORED_MEX_QUERY #include <cassert> #include <array> #include <type_traits> #include <limits> #include "library/datastructure/bit_vector.hpp" namespace suisen { template <typename T, int bit_num = std::numeric_limits<std::make_unsigned_t<T>>::digits> struct RangeXoredMexQuery { // default constructor RangeXoredMexQuery() noexcept : n(0) {} // builds WaveletMatrix from vector template <typename U, std::enable_if_t<std::is_constructible_v<T, U>, std::nullptr_t> = nullptr> RangeXoredMexQuery(const std::vector<U>& a) { build(a); } // builds WaveletMatrix from generating function typed as (int) -> T template <typename U, std::enable_if_t<std::is_constructible_v<T, U>, std::nullptr_t> = nullptr> void build(const std::vector<U> &dat) { n = dat.size(); std::vector<T> a(n), l(n), r(n); for (int i = 0; i < n; ++i) a[i] = dat[i]; int floor_log2 = 0; while (1 << (floor_log2 + 1) <= n) ++floor_log2; std::vector<int> cnt(1 << floor_log2, 0); int dcnt = 0; auto calc_min_r = [&, this](int log) { min_r[log].assign(n + 1, n + 1); if (log > floor_log2) return; const int mask = (1 << log) - 1; for (int l = 0, r = 0; l < n;) { while (r < n and dcnt != 1 << log) dcnt += ++cnt[a[r++] & mask] == 1; if (dcnt == 1 << log) min_r[log][l] = r; dcnt -= --cnt[a[l++] & mask] == 0; } }; calc_min_r(bit_num); 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; calc_min_r(log); } } // returns mex { A_i ^ x | l <= i < r } T minimum_excluded(int l, int r, T x) const { if (x >> bit_num) return 0; if (min_r[bit_num][l] <= r) return T(1) << bit_num; T res = 0; for (int log = bit_num - 1; log >= 0; --log) { bool z = (x >> log) & 1; auto [zl, zr] = succ(l, r, z, log); if (min_r[log][zl] <= zr) { std::tie(l, r) = succ(l, r, not z, log); res |= T(1) << log; } else { l = zl, r = zr; } } return res; } private: static_assert(bit_num > 0); int n; std::array<BitVector, bit_num> bv; std::array<int, bit_num> mid; std::array<std::vector<int>, bit_num + 1> min_r; std::pair<int, int> succ(int l, int r, const bool b, const int log) const { return std::make_pair(b * mid[log] + bv[log].rank(b, l), b * mid[log] + bv[log].rank(b, r)); } }; } // namespace suisen #endif // SUISEN_RANGE_XORED_MEX_QUERY
#line 1 "library/range_query/static_range_xored_mex_query.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 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/range_query/static_range_xored_mex_query.hpp" namespace suisen { template <typename T, int bit_num = std::numeric_limits<std::make_unsigned_t<T>>::digits> struct RangeXoredMexQuery { // default constructor RangeXoredMexQuery() noexcept : n(0) {} // builds WaveletMatrix from vector template <typename U, std::enable_if_t<std::is_constructible_v<T, U>, std::nullptr_t> = nullptr> RangeXoredMexQuery(const std::vector<U>& a) { build(a); } // builds WaveletMatrix from generating function typed as (int) -> T template <typename U, std::enable_if_t<std::is_constructible_v<T, U>, std::nullptr_t> = nullptr> void build(const std::vector<U> &dat) { n = dat.size(); std::vector<T> a(n), l(n), r(n); for (int i = 0; i < n; ++i) a[i] = dat[i]; int floor_log2 = 0; while (1 << (floor_log2 + 1) <= n) ++floor_log2; std::vector<int> cnt(1 << floor_log2, 0); int dcnt = 0; auto calc_min_r = [&, this](int log) { min_r[log].assign(n + 1, n + 1); if (log > floor_log2) return; const int mask = (1 << log) - 1; for (int l = 0, r = 0; l < n;) { while (r < n and dcnt != 1 << log) dcnt += ++cnt[a[r++] & mask] == 1; if (dcnt == 1 << log) min_r[log][l] = r; dcnt -= --cnt[a[l++] & mask] == 0; } }; calc_min_r(bit_num); 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; calc_min_r(log); } } // returns mex { A_i ^ x | l <= i < r } T minimum_excluded(int l, int r, T x) const { if (x >> bit_num) return 0; if (min_r[bit_num][l] <= r) return T(1) << bit_num; T res = 0; for (int log = bit_num - 1; log >= 0; --log) { bool z = (x >> log) & 1; auto [zl, zr] = succ(l, r, z, log); if (min_r[log][zl] <= zr) { std::tie(l, r) = succ(l, r, not z, log); res |= T(1) << log; } else { l = zl, r = zr; } } return res; } private: static_assert(bit_num > 0); int n; std::array<BitVector, bit_num> bv; std::array<int, bit_num> mid; std::array<std::vector<int>, bit_num + 1> min_r; std::pair<int, int> succ(int l, int r, const bool b, const int log) const { return std::make_pair(b * mid[log] + bv[log].rank(b, l), b * mid[log] + bv[log].rank(b, r)); } }; } // namespace suisen