結果
| 問題 | No.3101 Range Eratosthenes Query |
| ユーザー |
 otera
|
| 提出日時 | 2025-04-11 21:44:59 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 657 ms / 3,000 ms |
| コード長 | 21,408 bytes |
| コンパイル時間 | 2,094 ms |
| コンパイル使用メモリ | 206,732 KB |
| 実行使用メモリ | 50,540 KB |
| 最終ジャッジ日時 | 2025-04-11 21:45:17 |
| 合計ジャッジ時間 | 12,944 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 24 |
ソースコード
/**
* author: otera
**/
#include<bits/stdc++.h>
namespace otera {}
using namespace std;
using namespace otera;
struct io_setup {
io_setup(int precision = 20) {
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(precision);
}
} io_setup_ {};
#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 5 "library/type_traits/type_traits.hpp"
#include <iostream>
#line 7 "library/type_traits/type_traits.hpp"
namespace suisen {
template <typename ...Constraints> using constraints_t = std::enable_if_t<std::conjunction_v<Constraints...>, std::nullptr_t>;
template <typename T, typename = std::nullptr_t> struct bitnum { static constexpr int value = 0; };
template <typename T> struct bitnum<T, constraints_t<std::is_integral<T>>> { static constexpr int value = std::numeric_limits<std::make_unsigned_t<T>>::digits; };
template <typename T> static constexpr int bitnum_v = bitnum<T>::value;
template <typename T, size_t n> struct is_nbit { static constexpr bool value = bitnum_v<T> == n; };
template <typename T, size_t n> static constexpr bool is_nbit_v = is_nbit<T, n>::value;
template <typename T, typename = std::nullptr_t> struct safely_multipliable { using type = T; };
template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 32>>> { using type = long long; };
template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 64>>> { using type = __int128_t; };
template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 32>>> { using type = unsigned long long; };
template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 64>>> { using type = __uint128_t; };
template <typename T> using safely_multipliable_t = typename safely_multipliable<T>::type;
template <typename T, typename = void> struct rec_value_type { using type = T; };
template <typename T> struct rec_value_type<T, std::void_t<typename T::value_type>> {
using type = typename rec_value_type<typename T::value_type>::type;
};
template <typename T> using rec_value_type_t = typename rec_value_type<T>::type;
template <typename T> class is_iterable {
template <typename T_> static auto test(T_ e) -> decltype(e.begin(), e.end(), std::true_type{});
static std::false_type test(...);
public:
static constexpr bool value = decltype(test(std::declval<T>()))::value;
};
template <typename T> static constexpr bool is_iterable_v = is_iterable<T>::value;
template <typename T> class is_writable {
template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::ostream&>() << e, std::true_type{});
static std::false_type test(...);
public:
static constexpr bool value = decltype(test(std::declval<T>()))::value;
};
template <typename T> static constexpr bool is_writable_v = is_writable<T>::value;
template <typename T> class is_readable {
template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::istream&>() >> e, std::true_type{});
static std::false_type test(...);
public:
static constexpr bool value = decltype(test(std::declval<T>()))::value;
};
template <typename T> static constexpr bool is_readable_v = is_readable<T>::value;
} // namespace suisen
#line 8 "library/datastructure/bit_vector.hpp"
namespace suisen {
struct BitVector {
explicit BitVector(int n) : n(n), nl((n >> LOG_BLOCK_L) + 1), ns((n >> LOG_BLOCK_S) + 1), cum_l(nl, 0), cum_s(ns, 0), bits(ns, 0) {}
BitVector() : BitVector(0) {}
template <typename Gen, constraints_t<std::is_invocable_r<bool, Gen, int>> = nullptr>
BitVector(int n, Gen gen) : BitVector(n) {
build(gen);
}
BitVector& operator=(const BitVector& bv) {
n = bv.n, nl = bv.nl, ns = bv.ns, cum_l = bv.cum_l, cum_s = bv.cum_s, bits = bv.bits;
return *this;
}
BitVector& operator=(BitVector&& bv) {
n = bv.n, nl = bv.nl, ns = bv.ns, cum_l = std::move(bv.cum_l), cum_s = std::move(bv.cum_s), bits = std::move(bv.bits);
return *this;
}
template <typename Gen, constraints_t<std::is_invocable_r<bool, Gen, int>> = nullptr>
void build(Gen gen) {
int i = 0;
for (int index_s = 1; index_s < ns; ++index_s) {
int count = cum_s[index_s - 1];
for (; i < index_s << LOG_BLOCK_S; ++i) {
bool b = gen(i);
bits[index_s - 1] |= b << (i & MASK_S);
count += b;
}
if (index_s & ((1 << (LOG_BLOCK_L - LOG_BLOCK_S)) - 1)) {
cum_s[index_s] = count;
} else {
int index_l = i >> LOG_BLOCK_L;
cum_l[index_l] = cum_l[index_l - 1] + count;
}
}
for (; i < n; ++i) bits[ns - 1] |= gen(i) << (i & MASK_S);
}
bool operator[](int i) const {
return (bits[i >> LOG_BLOCK_S] >> (i & MASK_S)) & 1;
}
// returns the i'th val (i: 0-indexed)
bool access(int i) const {
return (*this)[i];
}
// returns the number of val in [0, i)
int rank(bool val, int i) const {
int res_1 = cum_l[i >> LOG_BLOCK_L] + cum_s[i >> LOG_BLOCK_S] + popcount8(bits[i >> LOG_BLOCK_S] & ((1 << (i & MASK_S)) - 1));
return val ? res_1 : i - res_1;
}
// returns the number of val in [l, r)
int rank(bool val, int l, int r) const {
return rank(val, r) - rank(val, l);
}
// find the index of num'th val. (num: 1-indexed). if not exists, returns default_value.
int select(bool val, int num, int default_value = -1) const {
int l = -1, r = n + 1;
while (r - l > 1) {
int m = (l + r) >> 1;
(rank(val, m) >= num ? r : l) = m;
}
return r == n + 1 ? default_value : r;
}
private:
static constexpr int LOG_BLOCK_L = 8;
static constexpr int LOG_BLOCK_S = 3;
static constexpr int MASK_S = (1 << LOG_BLOCK_S) - 1;
int n, nl, ns;
std::vector<int> cum_l;
std::vector<std::uint8_t> cum_s, bits;
static constexpr std::uint8_t popcount8(std::uint8_t x) {
x = (x & 0b01010101) + ((x >> 1) & 0b01010101);
x = (x & 0b00110011) + ((x >> 2) & 0b00110011);
return (x & 0b00001111) + (x >> 4);
}
};
} // namespace suisen
#line 10 "library/datastructure/wavelet_matrix.hpp"
namespace suisen {
template <typename T, int bit_num = std::numeric_limits<std::make_unsigned_t<T>>::digits>
struct WaveletMatrix {
// default constructor
WaveletMatrix() noexcept : n(0) {}
// builds WaveletMatrix from generating function typed as (int) -> T
template <typename Gen, constraints_t<std::is_invocable_r<T, Gen, int>> = nullptr>
WaveletMatrix(int n, Gen generator) : n(n) {
build(generator);
}
// builds WaveletMatrix from vector
template <typename U, constraints_t<std::is_constructible<T, U>> = nullptr>
WaveletMatrix(const std::vector<U>& a) : WaveletMatrix(a.size(), [&a](int i) { return T(a[i]); }) {}
// builds WaveletMatrix from generating function typed as (int) -> T
template <typename Gen, constraints_t<std::is_invocable_r<T, Gen, int>> = nullptr>
void build(Gen generator) {
std::vector<T> a(n), l(n), r(n);
for (int i = 0; i < n; ++i) a[i] = generator(i);
for (int log = bit_num - 1; log >= 0; --log) {
bv[log] = BitVector(n, [&a, log](int i) -> bool { return (a[i] >> log) & 1; });
int li = 0, ri = 0;
for (int i = 0; i < n; ++i) {
((a[i] >> log) & 1 ? r[ri++] : l[li++]) = a[i];
}
a.swap(l);
std::copy(r.begin(), r.begin() + ri, a.begin() + li);
mid[log] = li;
}
}
// returns WaveletMatrix[i]
T operator[](int i) const {
T res = 0;
for (int log = bit_num - 1; log >= 0; --log) {
bool b = bv[log][i];
res |= T(b) << log;
i = b * mid[log] + bv[log].rank(b, i);
}
return res;
}
// returns WaveletMatrix[i]
T access(int i) const {
return (*this)[i];
}
// returns the number of `val` in WaveletMatrix[0, i).
int rank(T val, int i) const {
check_value_bounds(val);
int l = 0, r = i;
for (int log = bit_num - 1; log >= 0; --log) succ(l, r, (val >> log) & 1, log);
return r - l;
}
// returns the k'th smallest value in the multiset {| x ^ WaveletMatrix[i] : i in [l, r) |} (k : 0-indexed)
T range_xor_kth_smallest(int l, int r, int k, T x, T default_value = T(-1)) const {
if (k < 0 or k >= r - l) return default_value;
T res = 0;
check_value_bounds(x);
for (int log = bit_num - 1; log >= 0; --log) {
bool z = (x >> log) & 1;
int cnt_z = bv[log].rank(z, l, r);
bool skip_z = k >= cnt_z, bit = z ^ skip_z;
succ(l, r, bit, log);
res |= T(bit) << log;
k -= skip_z * cnt_z;
}
return res;
}
// returns the k'th largest value in the multiset {| x ^ WaveletMatrix[i] : i in [l, r) |} (k : 0-indexed)
T range_xor_kth_largest(int l, int r, int k, T x, T default_value = T(-1)) const {
return range_xor_kth_smallest(l, r, r - l - 1 - k, x, default_value);
}
// returns the minimum value in the set { x ^ WaveletMatrix[i] : i in [l, r) }
T range_xor_min(int l, int r, T x) const {
assert(l < r);
return range_xor_kth_smallest(l, r, 0, x);
}
// returns the maximum value in the set { x ^ WaveletMatrix[i] : i in [l, r) }
T range_xor_max(int l, int r, T x) const {
assert(l < r);
return range_xor_kth_largest(l, r, 0, x);
}
// returns the number of v in WaveletMatrix[l, r) s.t. v ^ x < upper
int range_xor_freq(int l, int r, T x, T upper) const {
if (r <= l) return 0;
if (upper > MAX) return r - l;
check_value_bounds(x);
int res = 0;
for (int log = bit_num - 1; log >= 0; --log) {
bool z = (x >> log) & 1, u = (upper >> log) & 1;
if (u) res += bv[log].rank(z, l, r);
succ(l, r, z ^ u, log);
}
return res;
}
// returns the number of v in WaveletMatrix[l, r) s.t. lower <= x ^ v < upper
int range_xor_freq(int l, int r, T x, T lower, T upper) const {
if (lower >= upper) return 0;
return range_xor_freq(l, r, x, upper) - range_xor_freq(l, r, x, lower);
}
// returns the minimum value v in WaveletMatrix[l, r) s.t. lower <= x ^ v
T range_xor_min_geq(int l, int r, T x, T lower, T default_value = T(-1)) const {
int cnt = range_xor_freq(l, r, x, lower);
return cnt >= r - l ? default_value : range_xor_kth_smallest(l, r, cnt, x);
}
// returns the minimum value v in WaveletMatrix[l, r) s.t. lower < x ^ v
T range_xor_min_gt(int l, int r, T x, T lower, T default_value = T(-1)) const {
return lower == MAX ? default_value : range_xor_min_geq(l, r, x, lower + 1, default_value);
}
// returns the maximum value v in WaveletMatrix[l, r) s.t. x ^ v < upper
T range_xor_max_lt(int l, int r, T x, T upper, T default_value = T(-1)) const {
int cnt = range_xor_freq(l, r, x, upper);
return cnt == 0 ? default_value : range_xor_kth_smallest(l, r, cnt - 1, x, default_value);
}
// returns the maximum value v in WaveletMatrix[l, r) s.t. x ^ v <= upper
T range_xor_max_leq(int l, int r, T x, T upper, T default_value = T(-1)) const {
if (l >= r) return default_value;
return upper == MAX ? range_xor_max(l, r, x) : range_xor_max_lt(l, r, x, upper + 1, default_value);
}
// returns the k'th smallest value in WaveletMatrix[l, r) (k : 0-indexed)
T range_kth_smallest(int l, int r, int k, T default_value = T(-1)) const { return range_xor_kth_smallest(l, r, k, 0, default_value); }
// returns the k'th largest value in WaveletMatrix[l, r) (k : 0-indexed)
T range_kth_largest(int l, int r, int k, T default_value = T(-1)) const { return range_xor_kth_largest(l, r, k, 0, default_value); }
// returns the minimum value in WaveletMatrix[l, r)
T range_min(int l, int r) const { return range_xor_min(l, r, 0); }
// returns the maximum value in WaveletMatrix[l, r)
T range_max(int l, int r) const { return range_xor_max(l, r, 0); }
// returns the number of v in WaveletMatrix[l, r) s.t. v < upper
int range_freq(int l, int r, T upper) const { return range_xor_freq(l, r, 0, upper); }
// returns the number of v in WaveletMatrix[l, r) s.t. lower <= v < upper
int range_freq(int l, int r, T lower, T upper) const { return range_xor_freq(l, r, 0, lower, upper); }
// returns the minimum value v in WaveletMatrix[l, r) s.t. lower <= v
T range_min_geq(int l, int r, T lower, T default_value = T(-1)) const { return range_xor_min_geq(l, r, 0, lower, default_value); }
// returns the minimum value v in WaveletMatrix[l, r) s.t. lower < v
T range_min_gt(int l, int r, T lower, T default_value = T(-1)) const { return range_xor_min_gt(l, r, 0, lower, default_value); }
// returns the maximum value v in WaveletMatrix[l, r) s.t. v < upper
T range_max_lt(int l, int r, T upper, T default_value = T(-1)) const { return range_xor_max_lt(l, r, 0, upper, default_value); }
// returns the maximum value v in WaveletMatrix[l, r) s.t. v <= upper
T range_max_leq(int l, int r, T upper, T default_value = T(-1)) const { return range_xor_max_leq(l, r, 0, upper, default_value); }
protected:
WaveletMatrix(int n) noexcept : n(n) {}
private:
static_assert(bit_num > 0);
static constexpr T MAX = bit_num == std::numeric_limits<T>::digits ? std::numeric_limits<T>::max() : (T(1) << bit_num) - 1;
int n;
std::array<BitVector, bit_num> bv;
std::array<int, bit_num> mid;
void succ(int& l, int& r, const bool b, const int log) const {
l = b * mid[log] + bv[log].rank(b, l);
r = b * mid[log] + bv[log].rank(b, r);
}
static void check_value_bounds(T val) {
assert((val >> bit_num) == 0);
}
};
} // namespace suisen
#define int long long
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
#define repa(i, n) for(int i = 0; i < (n); ++ i)
#define repb(i, a, b) for(int i = (a); i < (b); ++ i)
#define repc(i, a, b, c) for(int i = (a); i < (b); i += (c))
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define rep(...) overload4(__VA_ARGS__, repc, repb, repa)(__VA_ARGS__)
#define rep1a(i, n) for(int i = 1; i <= (n); ++ i)
#define rep1b(i, a, b) for(int i = (a); i <= (b); ++ i)
#define rep1c(i, a, b, c) for(int i = (a); i <= (b); i += (c))
#define rep1(...) overload4(__VA_ARGS__, rep1c, rep1b, rep1a)(__VA_ARGS__)
#define rev_repa(i, n) for(int i=(n)-1;i>=0;i--)
#define rev_repb(i, a, b) for(int i=(b)-1;i>=(a);i--)
#define rev_rep(...) overload3(__VA_ARGS__, rev_repb, rev_repa)(__VA_ARGS__)
#define rev_rep1a(i, n) for(int i=(n);i>=1;i--)
#define rev_rep1b(i, a, b) for(int i=(b);i>=(a);i--)
#define rev_rep1(...) overload3(__VA_ARGS__, rev_rep1b, rev_rep1a)(__VA_ARGS__)
#define for_subset(t, s) for(ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define eb emplace_back
#define mkp make_pair
#define mkt make_tuple
#define fr first
#define sc second
#define all(c) std::begin(c), std::end(c)
#define rall(c) std::rbegin(c), std::rend(c)
#define lb(c, x) distance(std::begin(c), lower_bound(all(c), (x)))
#define ub(c, x) distance(std::begin(c), upper_bound(all(c), (x)))
#define Sort(a) sort(all(a))
#define Rev(a) reverse(all(a))
#define Uniq(a) sort(all(a));(a).erase(unique(all(a)),std::end(a))
#define si(c) (int)(c).size()
inline ll popcnt(ull a){ return __builtin_popcountll(a); }
#define kth_bit(x, k) ((x>>k)&1)
#define unless(A) if(!(A))
#define elif else if
ll modulo(ll n, ll d){ return (n % d + d) % d; };
ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }
ll intpow(ll a, ll b, ll m) {ll ans = 1; while(b){ if(b & 1) (ans *= a) %= m; (a *= a) %= m; b /= 2; } return ans; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> constexpr inline int pow_m1(T n) { return -(n & 1) | 1; }
template <typename T> constexpr inline T fld(const T x, const T y) { return (x ^ y) >= 0 ? x / y : (x - (y + pow_m1(y >= 0))) / y; }
template <typename T> constexpr inline T cld(const T x, const T y) { return (x ^ y) <= 0 ? x / y : (x + (y + pow_m1(y >= 0))) / y; }
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;in(__VA_ARGS__)
#define vec(type,name,...) vector<type>name(__VA_ARGS__)
#define VEC(type,name,size) vector<type>name(size);in(name)
#define vv(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define VV(type,name,h,w) vector<vector<type>>name(h,vector<type>(w));in(name)
#define vvv(type,name,h,w,...) vector<vector<vector<type>>>name(h,vector<vector<type>>(w,vector<type>(__VA_ARGS__)))
template <class T> using vc = vector<T>;
template <class T> using vvc = vector<vc<T>>;
template <class T> using vvvc = vector<vvc<T>>;
template <class T> using vvvvc = vector<vvvc<T>>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
template <class T, class U> using umap = unordered_map<T, U>;
template<class T> void scan(T& a){ cin >> a; }
template<class T> void scan(vector<T>& a){ for(auto&& i : a) scan(i); }
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail){ scan(head); in(tail...); }
void print(){ cout << ' '; }
template<class T> void print(const T& a){ cout << a; }
template<class T> void print(const vector<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ cout << ' '; print(*i); } }
int out(){ cout << '\n'; return 0; }
template<class T> int out(const T& t){ print(t); cout << '\n'; return 0; }
template<class Head, class... Tail> int out(const Head& head, const Tail&... tail){ print(head); cout << ' '; out(tail...); return 0; }
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,a4,x,...) x
#define debug_1(x1) cout<<#x1<<": "<<x1<<endl
#define debug_2(x1,x2) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<endl
#define debug_3(x1,x2,x3) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<endl
#define debug_4(x1,x2,x3,x4) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<endl
#define debug_5(x1,x2,x3,x4,x5) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<", "#x5<<": "<<x5<<endl
#ifdef DEBUG
#define debug(...) CHOOSE((__VA_ARGS__,debug_5,debug_4,debug_3,debug_2,debug_1,~))(__VA_ARGS__)
#define dump(...) { print(#__VA_ARGS__); print(":"); out(__VA_ARGS__); }
#else
#define debug(...)
#define dump(...)
#endif
const int A = 1e6 + 100;
void solve() {
vc<int> check(A, -1);
for(int x = 2; x < A; ++ x) {
for(int y = x; y < A; y += x) {
if(check[y] == -1) check[y] = x;
}
}
vc<int> a(A, 1);
for(int x = 2; x < A; ++ x) {
a[x] = x / check[x];
}
suisen::WaveletMatrix<int, 32> wm(a);
INT(q);
rep(_, q) {
INT(l, r); ++ r;
// [l, r)
int len = r - l;
if(l == 1) {
out(1);
} else {
int ans = wm.range_freq(l, r, 1, l);
out(ans);
}
}
}
signed main() {
int testcase = 1;
// in(testcase);
while(testcase--) solve();
return 0;
}