cp-library-cpp
This documentation is automatically generated by online-judge-tools/verification-helper
test/src/range_query/static_range_xored_mex_query/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)
- Static Range Xored Mex Query
(library/range_query/static_range_xored_mex_query.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/range_query/static_range_xored_mex_query.hpp"
template <typename T>
struct NaiveSolution {
NaiveSolution() = default;
NaiveSolution(const std::vector<T> &dat) : dat(dat) {}
T minimum_excluded(int l, int r, T x) {
std::vector<T> st;
for (int i = l; i < r; ++i) st.push_back(dat[i] ^ x);
std::sort(st.begin(), st.end());
st.erase(std::unique(st.begin(), st.end()), st.end());
st.push_back(std::numeric_limits<int>::max());
for (int i = 0;; ++i) {
if (st[i] != i) return i;
}
}
private:
std::vector<T> dat;
};
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);
suisen::RangeXoredMexQuery<T, bit_num> wm(dat);
NaiveSolution<T> naive(dat);
for (int l = 0; l <= n; ++l) for (int r = l; r <= n; ++r) {
for (int t = 0; t < q; ++t) {
int x = value_dist(rng);
assert(wm.minimum_excluded(l, r, x) == naive.minimum_excluded(l, r, x));
}
}
std::cerr << "done" << std::endl;
}
void tests() {
// std::vector<int> dat { 0, 1, 2, 3, 4 };
// suisen::RangeXoredMexQuery<int, 3> wm(dat);
// NaiveSolution<int> naive(dat);
// for (int l = 0; l <= 5; ++l) for (int r = l; r <= 5; ++r) {
// for (int x = 0; x <= 5; ++x) {
// std::cerr << "sub array : [";
// for (int i = l; i < r; ++i) {
// std::cerr << (dat[i] ^ x);
// if (i < r - 1) std::cerr << ",";
// }
// std::cerr << "]" << std::endl;
// int mex1 = wm.minimum_excluded(l, r, x);
// std::cerr << "actual : " << mex1 << std::endl;
// int mex2 = naive.minimum_excluded(l, r, x);
// std::cerr << "expected : " << mex2 << std::endl;
// }
// }
test<int, 1>(100, 100);
test<int, 2>(100, 100);
test<int, 3>(100, 100);
test<int, 4>(100, 100);
test<int, 5>(100, 100);
test<int, 6>(100, 100);
}
int main() {
tests();
std::cout << "Hello World" << std::endl;
return 0;
}#line 1 "test/src/range_query/static_range_xored_mex_query/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/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 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
#line 8 "test/src/range_query/static_range_xored_mex_query/dummy.test.cpp"
template <typename T>
struct NaiveSolution {
NaiveSolution() = default;
NaiveSolution(const std::vector<T> &dat) : dat(dat) {}
T minimum_excluded(int l, int r, T x) {
std::vector<T> st;
for (int i = l; i < r; ++i) st.push_back(dat[i] ^ x);
std::sort(st.begin(), st.end());
st.erase(std::unique(st.begin(), st.end()), st.end());
st.push_back(std::numeric_limits<int>::max());
for (int i = 0;; ++i) {
if (st[i] != i) return i;
}
}
private:
std::vector<T> dat;
};
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);
suisen::RangeXoredMexQuery<T, bit_num> wm(dat);
NaiveSolution<T> naive(dat);
for (int l = 0; l <= n; ++l) for (int r = l; r <= n; ++r) {
for (int t = 0; t < q; ++t) {
int x = value_dist(rng);
assert(wm.minimum_excluded(l, r, x) == naive.minimum_excluded(l, r, x));
}
}
std::cerr << "done" << std::endl;
}
void tests() {
// std::vector<int> dat { 0, 1, 2, 3, 4 };
// suisen::RangeXoredMexQuery<int, 3> wm(dat);
// NaiveSolution<int> naive(dat);
// for (int l = 0; l <= 5; ++l) for (int r = l; r <= 5; ++r) {
// for (int x = 0; x <= 5; ++x) {
// std::cerr << "sub array : [";
// for (int i = l; i < r; ++i) {
// std::cerr << (dat[i] ^ x);
// if (i < r - 1) std::cerr << ",";
// }
// std::cerr << "]" << std::endl;
// int mex1 = wm.minimum_excluded(l, r, x);
// std::cerr << "actual : " << mex1 << std::endl;
// int mex2 = naive.minimum_excluded(l, r, x);
// std::cerr << "expected : " << mex2 << std::endl;
// }
// }
test<int, 1>(100, 100);
test<int, 2>(100, 100);
test<int, 3>(100, 100);
test<int, 4>(100, 100);
test<int, 5>(100, 100);
test<int, 6>(100, 100);
}
int main() {
tests();
std::cout << "Hello World" << std::endl;
return 0;
}