結果
問題 | No.3101 Range Eratosthenes Query |
ユーザー |
|
提出日時 | 2025-04-11 23:17:34 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 255 ms / 3,000 ms |
コード長 | 27,270 bytes |
コンパイル時間 | 2,102 ms |
コンパイル使用メモリ | 154,032 KB |
実行使用メモリ | 28,564 KB |
最終ジャッジ日時 | 2025-04-11 23:17:55 |
合計ジャッジ時間 | 8,472 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 24 |
ソースコード
#include <deque> #include <cassert> #include <array> #include <set> #include <iterator> #include <bitset> #include <functional> #include <unordered_map> #include <string> #include <utility> #include <vector> #include <queue> #include <iomanip> #include <istream> #include <type_traits> #include <numeric> #include <algorithm> #include <fstream> #include <unordered_set> #include <ostream> #include <stack> #include <map> #include <iostream> #include <optional> #ifndef KK2_TEMPLATE_PROCON_HPP #define KK2_TEMPLATE_PROCON_HPP 1 #ifndef KK2_TEMPLATE_CONSTANT_HPP #define KK2_TEMPLATE_CONSTANT_HPP 1 #ifndef KK2_TEMPLATE_TYPE_ALIAS_HPP #define KK2_TEMPLATE_TYPE_ALIAS_HPP 1 using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; using i128 = __int128_t; using u128 = __uint128_t; using pi = std::pair<int, int>; using pl = std::pair<i64, i64>; using pil = std::pair<int, i64>; using pli = std::pair<i64, int>; template <class T> using vc = std::vector<T>; template <class T> using vvc = std::vector<vc<T>>; template <class T> using vvvc = std::vector<vvc<T>>; template <class T> using vvvvc = std::vector<vvvc<T>>; template <class T> using pq = std::priority_queue<T>; template <class T> using pqi = std::priority_queue<T, std::vector<T>, std::greater<T>>; #endif // KK2_TEMPLATE_TYPE_ALIAS_HPP template <class T> constexpr T infty = 0; template <> constexpr int infty<int> = (1 << 30) - 123; template <> constexpr i64 infty<i64> = (1ll << 62) - (1ll << 31); template <> constexpr i128 infty<i128> = (i128(1) << 126) - (i128(1) << 63); template <> constexpr u32 infty<u32> = infty<int>; template <> constexpr u64 infty<u64> = infty<i64>; template <> constexpr u128 infty<u128> = infty<i128>; template <> constexpr double infty<double> = infty<i64>; template <> constexpr long double infty<long double> = infty<i64>; constexpr int mod = 998244353; constexpr int modu = 1e9 + 7; constexpr long double PI = 3.14159265358979323846; #endif // KK2_TEMPLATE_CONSTANT_HPP #ifndef KK2_TEMPLATE_FUNCTION_UTIL_HPP #define KK2_TEMPLATE_FUNCTION_UTIL_HPP 1 #ifndef KK2_MATH_MONOID_MAX_HPP #define KK2_MATH_MONOID_MAX_HPP 1 #ifndef KK2_TYPE_TRAITS_IO_HPP #define KK2_TYPE_TRAITS_IO_HPP 1 namespace kk2 { namespace type_traits { struct istream_tag {}; struct ostream_tag {}; } // namespace type_traits template <typename T> using is_standard_istream = typename std::conditional<std::is_same<T, std::istream>::value || std::is_same<T, std::ifstream>::value, std::true_type, std::false_type>::type; template <typename T> using is_standard_ostream = typename std::conditional<std::is_same<T, std::ostream>::value || std::is_same<T, std::ofstream>::value, std::true_type, std::false_type>::type; template <typename T> using is_user_defined_istream = std::is_base_of<type_traits::istream_tag, T>; template <typename T> using is_user_defined_ostream = std::is_base_of<type_traits::ostream_tag, T>; template <typename T> using is_istream = typename std::conditional<is_standard_istream<T>::value || is_user_defined_istream<T>::value, std::true_type, std::false_type>::type; template <typename T> using is_ostream = typename std::conditional<is_standard_ostream<T>::value || is_user_defined_ostream<T>::value, std::true_type, std::false_type>::type; template <typename T> using is_istream_t = std::enable_if_t<is_istream<T>::value>; template <typename T> using is_ostream_t = std::enable_if_t<is_ostream<T>::value>; } // namespace kk2 #endif // KK2_TYPE_TRAITS_IO_HPP namespace kk2 { namespace monoid { template <class S, class Compare = std::less<S>> struct Max { static constexpr bool commutative = true; using M = Max; S a; bool is_unit; Max() : a(S()), is_unit(true) {} Max(S a_) : a(a_), is_unit(false) {} operator S() const { return a; } inline static M op(M l, M r) { if (l.is_unit or r.is_unit) return l.is_unit ? r : l; return Compare{}(l.a, r.a) ? r : l; } inline static M unit() { return M(); } bool operator==(const M &rhs) const { return is_unit == rhs.is_unit and (is_unit or a == rhs.a); } bool operator!=(const M &rhs) const { return is_unit != rhs.is_unit or (!is_unit and a != rhs.a); } template <class OStream, is_ostream_t<OStream> * = nullptr> friend OStream &operator<<(OStream &os, const M &x) { if (x.is_unit) os << "-inf"; else os << x.a; return os; } template <class IStream, is_istream_t<IStream> * = nullptr> friend IStream &operator>>(IStream &is, M &x) { is >> x.a; x.is_unit = false; return is; } }; } // namespace monoid } // namespace kk2 #endif // MATH_MONOID_MAX_HPP #ifndef KK2_MATH_MONOID_MIN_HPP #define KK2_MATH_MONOID_MIN_HPP 1 namespace kk2 { namespace monoid { template <class S, class Compare = std::less<S>> struct Min { static constexpr bool commutative = true; using M = Min; S a; bool is_unit; Min() : a(S()), is_unit(true) {} Min(S a_) : a(a_), is_unit(false) {} operator S() const { return a; } inline static M op(M l, M r) { if (l.is_unit or r.is_unit) return l.is_unit ? r : l; return Compare{}(l.a, r.a) ? l : r; } inline static M unit() { return M(); } bool operator==(const M &rhs) const { return is_unit == rhs.is_unit and (is_unit or a == rhs.a); } bool operator!=(const M &rhs) const { return is_unit != rhs.is_unit or (!is_unit and a != rhs.a); } template <class OStream, is_ostream_t<OStream> * = nullptr> friend OStream &operator<<(OStream &os, const M &x) { if (x.is_unit) os << "inf"; else os << x.a; return os; } template <class IStream, is_istream_t<IStream> * = nullptr> friend IStream &operator>>(IStream &is, M &x) { is >> x.a; x.is_unit = false; return is; } }; } // namespace monoid } // namespace kk2 #endif // KK2_MATH_MONOID_MIN_HPP #ifndef KK2_TYPE_TRAITS_CONTAINER_TRAITS_HPP #define KK2_TYPE_TRAITS_CONTAINER_TRAITS_HPP 1 namespace kk2 { template <typename T> struct is_vector : std::false_type {}; template <typename T, typename Alloc> struct is_vector<std::vector<T, Alloc>> : std::true_type {}; } // namespace kk2 #endif // KK2_TYPE_TRAITS_CONTAINER_TRAITS_HPP namespace kk2 { template <class T, class... Sizes> auto make_vector(int first, Sizes... sizes) { if constexpr (sizeof...(sizes) == 0) { return std::vector<T>(first); } else { return std::vector<decltype(make_vector<T>(sizes...))>(first, make_vector<T>(sizes...)); } } template <class T, class U> void fill_all(std::vector<T> &v, const U &x) { if constexpr (is_vector<T>::value) { for (auto &u : v) fill_all(u, x); } else { std::fill(v.begin(), v.end(), T(x)); } } template <class T, class U> int iota_all(std::vector<T> &v, U x, int offset = 0) { if constexpr (is_vector<T>::value) { for (auto &u : v) offset += iota_all(u, x + offset); } else { for (auto &u : v) u = x++, ++offset; } return offset; } template <class C> int mysize(const C &c) { return size(c); } // T: commutative monoid, F: (U, T) -> U template <class U, class T, class F> U all_monoid_prod(const std::vector<T> &v, U unit, const F &f) { U res = unit; if constexpr (is_vector<T>::value) { for (const auto &x : v) res = f(res, all_monoid_prod(x, unit, f)); } else { for (const auto &x : v) res = f(res, x); } return res; } template <class U, class T> U all_sum(const std::vector<T> &v, U unit = U()) { return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a + b; }); } template <class U, class T> U all_prod(const std::vector<T> &v, U unit = U(1)) { return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a * b; }); } template <class U, class T> U all_xor(const std::vector<T> &v, U unit = U()) { return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a ^ b; }); } template <class U, class T> U all_and(const std::vector<T> &v, U unit = U(-1)) { return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a & b; }); } template <class U, class T> U all_or(const std::vector<T> &v, U unit = U()) { return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a | b; }); } template <class U, class T> U all_min(const std::vector<T> &v) { return all_monoid_prod<monoid::Min<U>, T>(v, monoid::Min<U>::unit(), monoid::Min<U>::op); } template <class U, class T> U all_max(const std::vector<T> &v) { return all_monoid_prod<monoid::Max<U>, T>(v, monoid::Max<U>::unit(), monoid::Max<U>::op); } template <class U, class T> U all_gcd(const std::vector<T> &v, U unit = U()) { return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return std::gcd(a, b); }); } template <class U, class T> U all_lcm(const std::vector<T> &v, U unit = U(1)) { return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return std::lcm(a, b); }); } } // namespace kk2 #endif // KK2_TEMPLATE_FUNCTION_UTIL_HPP #ifndef KK2_TEMPLATE_IO_UTIL_HPP #define KK2_TEMPLATE_IO_UTIL_HPP 1 // なんかoj verifyはプロトタイプ宣言が落ちる namespace impl { struct read { template <class IStream, class T> inline static void all_read(IStream &is, T &x) { is >> x; } template <class IStream, class T, class U> inline static void all_read(IStream &is, std::pair<T, U> &p) { all_read(is, p.first); all_read(is, p.second); } template <class IStream, class T> inline static void all_read(IStream &is, std::vector<T> &v) { for (T &x : v) all_read(is, x); } template <class IStream, class T, size_t F> inline static void all_read(IStream &is, std::array<T, F> &a) { for (T &x : a) all_read(is, x); } }; struct write { template <class OStream, class T> inline static void all_write(OStream &os, const T &x) { os << x; } template <class OStream, class T, class U> inline static void all_write(OStream &os, const std::pair<T, U> &p) { all_write(os, p.first); all_write(os, ' '); all_write(os, p.second); } template <class OStream, class T> inline static void all_write(OStream &os, const std::vector<T> &v) { for (int i = 0; i < (int)v.size(); ++i) { if (i) all_write(os, ' '); all_write(os, v[i]); } } template <class OStream, class T, size_t F> inline static void all_write(OStream &os, const std::array<T, F> &a) { for (int i = 0; i < (int)F; ++i) { if (i) all_write(os, ' '); all_write(os, a[i]); } } }; } // namespace impl template <class IStream, class T, class U, kk2::is_istream_t<IStream> * = nullptr> IStream &operator>>(IStream &is, std::pair<T, U> &p) { impl::read::all_read(is, p); return is; } template <class IStream, class T, kk2::is_istream_t<IStream> * = nullptr> IStream &operator>>(IStream &is, std::vector<T> &v) { impl::read::all_read(is, v); return is; } template <class IStream, class T, size_t F, kk2::is_istream_t<IStream> * = nullptr> IStream &operator>>(IStream &is, std::array<T, F> &a) { impl::read::all_read(is, a); return is; } template <class OStream, class T, class U, kk2::is_ostream_t<OStream> * = nullptr> OStream &operator<<(OStream &os, const std::pair<T, U> &p) { impl::write::all_write(os, p); return os; } template <class OStream, class T, kk2::is_ostream_t<OStream> * = nullptr> OStream &operator<<(OStream &os, const std::vector<T> &v) { impl::write::all_write(os, v); return os; } template <class OStream, class T, size_t F, kk2::is_ostream_t<OStream> * = nullptr> OStream &operator<<(OStream &os, const std::array<T, F> &a) { impl::write::all_write(os, a); return os; } #endif // KK2_TEMPLATE_IO_UTIL_HPP #ifndef KK2_TEMPLATE_MACROS_HPP #define KK2_TEMPLATE_MACROS_HPP 1 #define rep1(a) for (long long _ = 0; _ < (long long)(a); ++_) #define rep2(i, a) for (long long i = 0; i < (long long)(a); ++i) #define rep3(i, a, b) for (long long i = (a); i < (long long)(b); ++i) #define repi2(i, a) for (long long i = (a) - 1; i >= 0; --i) #define repi3(i, a, b) for (long long i = (a) - 1; i >= (long long)(b); --i) #define overload3(a, b, c, d, ...) d #define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #define repi(...) overload3(__VA_ARGS__, repi3, repi2, rep1)(__VA_ARGS__) #define fi first #define se second #define all(p) begin(p), end(p) #endif // KK2_TEMPLATE_MACROS_HPP struct FastIOSetUp { FastIOSetUp() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } } fast_io_set_up; auto &kin = std::cin; auto &kout = std::cout; auto (*kendl)(std::ostream &) = std::endl<char, std::char_traits<char>>; void Yes(bool b = 1) { kout << (b ? "Yes\n" : "No\n"); } void No(bool b = 1) { kout << (b ? "No\n" : "Yes\n"); } void YES(bool b = 1) { kout << (b ? "YES\n" : "NO\n"); } void NO(bool b = 1) { kout << (b ? "NO\n" : "YES\n"); } void yes(bool b = 1) { kout << (b ? "yes\n" : "no\n"); } void no(bool b = 1) { kout << (b ? "no\n" : "yes\n"); } template <class T, class S> inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); } template <class T, class S> inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); } std::istream &operator>>(std::istream &is, u128 &x) { std::string s; is >> s; x = 0; for (char c : s) { assert('0' <= c && c <= '9'); x = x * 10 + c - '0'; } return is; } std::istream &operator>>(std::istream &is, i128 &x) { std::string s; is >> s; bool neg = s[0] == '-'; x = 0; for (int i = neg; i < (int)s.size(); i++) { assert('0' <= s[i] && s[i] <= '9'); x = x * 10 + s[i] - '0'; } if (neg) x = -x; return is; } std::ostream &operator<<(std::ostream &os, u128 x) { if (x == 0) return os << '0'; std::string s; while (x) { s.push_back('0' + x % 10); x /= 10; } std::reverse(s.begin(), s.end()); return os << s; } std::ostream &operator<<(std::ostream &os, i128 x) { if (x == 0) return os << '0'; if (x < 0) { os << '-'; x = -x; } std::string s; while (x) { s.push_back('0' + x % 10); x /= 10; } std::reverse(s.begin(), s.end()); return os << s; } #endif // KK2_TEMPLATE_PROCON_HPP // #include <kk2/template/debug.hpp> #ifndef KK2_DATA_STRUCTURE_WAVELET_MATRIX_HPP #define KK2_DATA_STRUCTURE_WAVELET_MATRIX_HPP 1 #ifndef KK2_BIT_BITCOUNT_HPP #define KK2_BIT_BITCOUNT_HPP 1 #ifndef KK2_TYPE_TRAITS_INTERGRAL_HPP #define KK2_TYPE_TRAITS_INTERGRAL_HPP 1 namespace kk2 { #ifndef _MSC_VER template <typename T> using is_signed_int128 = typename std::conditional<std::is_same<T, __int128_t>::value or std::is_same<T, __int128>::value, std::true_type, std::false_type>::type; template <typename T> using is_unsigned_int128 = typename std::conditional<std::is_same<T, __uint128_t>::value or std::is_same<T, unsigned __int128>::value, std::true_type, std::false_type>::type; template <typename T> using is_integral = typename std::conditional<std::is_integral<T>::value or is_signed_int128<T>::value or is_unsigned_int128<T>::value, std::true_type, std::false_type>::type; template <typename T> using is_signed = typename std::conditional<std::is_signed<T>::value or is_signed_int128<T>::value, std::true_type, std::false_type>::type; template <typename T> using is_unsigned = typename std::conditional<std::is_unsigned<T>::value or is_unsigned_int128<T>::value, std::true_type, std::false_type>::type; template <typename T> using make_unsigned_int128 = typename std::conditional<std::is_same<T, __int128_t>::value, __uint128_t, unsigned __int128>; template <typename T> using to_unsigned = typename std::conditional<is_signed_int128<T>::value, make_unsigned_int128<T>, typename std::conditional<std::is_signed<T>::value, std::make_unsigned<T>, std::common_type<T>>::type>::type; #else template <typename T> using is_integral = std::enable_if_t<std::is_integral<T>::value>; template <typename T> using is_signed = std::enable_if_t<std::is_signed<T>::value>; template <typename T> using is_unsigned = std::enable_if_t<std::is_unsigned<T>::value>; template <typename T> using to_unsigned = std::make_unsigned<T>; #endif // _MSC_VER template <typename T> using is_integral_t = std::enable_if_t<is_integral<T>::value>; template <typename T> using is_signed_t = std::enable_if_t<is_signed<T>::value>; template <typename T> using is_unsigned_t = std::enable_if_t<is_unsigned<T>::value>; } // namespace kk2 #endif // KK2_TYPE_TRAITS_INTERGRAL_HPP namespace kk2 { template <typename T> int ctz(T x) { static_assert(is_integral<T>::value); assert(x != T(0)); if constexpr (sizeof(T) <= 4) { return __builtin_ctz(x); } else if constexpr (sizeof(T) <= 8) { return __builtin_ctzll(x); } else { if (x & 0xffffffffffffffff) return __builtin_ctzll((unsigned long long)(x & 0xffffffffffffffff)); return 64 + __builtin_ctzll((unsigned long long)(x >> 64)); } } template <typename T> int lsb(T x) { static_assert(is_integral<T>::value); assert(x != T(0)); return ctz(x); } template <typename T> int clz(T x) { static_assert(is_integral<T>::value); assert(x != T(0)); if constexpr (sizeof(T) <= 4) { return __builtin_clz(x); } else if constexpr (sizeof(T) <= 8) { return __builtin_clzll(x); } else { if (x >> 64) return __builtin_clzll((unsigned long long)(x >> 64)); return 64 + __builtin_clzll((unsigned long long)(x & 0xffffffffffffffff)); } } template <typename T> int msb(T x) { static_assert(is_integral<T>::value); assert(x != T(0)); return sizeof(T) * 8 - 1 - clz(x); } template <typename T> int popcount(T x) { static_assert(is_integral<T>::value); if constexpr (sizeof(T) <= 4) { return __builtin_popcount(x); } else if constexpr (sizeof(T) <= 8) { return __builtin_popcountll(x); } else { return __builtin_popcountll((unsigned long long)(x >> 64)) + __builtin_popcountll((unsigned long long)(x & 0xffffffffffffffff)); } } }; // namespace kk2 #endif // KK2_BIT_BITCOUNT_HPP #ifndef KK2_DATA_STRUCTURE_BIT_VECTOR_HPP #define KK2_DATA_STRUCTURE_BIT_VECTOR_HPP 1 namespace kk2 { struct BitVector { using u32 = unsigned int; using Uint = unsigned long long; static constexpr int B = 64; int n, zeros; std::vector<u32> count; std::vector<Uint> bits; BitVector() = default; BitVector(int n_) : n(n_), count(n_ / B + 1), bits(n_ / B + 1) {} inline void set(int i) { bits[i / B] |= Uint(1) << (i % B); } void build() { for (u32 i = 1; i < count.size(); ++i) count[i] = count[i - 1] + popcount(bits[i - 1]); zeros = n - rank1(n); } inline int get(int i) const { return (bits[i / B] >> (i % B)) & 1; } inline int rank0(int i) const { return i - rank1(i); } inline int rank1(int i) const { return count[i / B] + popcount(bits[i / B] & ((Uint(1) << (i % B)) - 1)); } int select0(int i) const { if (i >= zeros) return -1; int lb = 0, ub = n; while (ub - lb > 1) { int mid = (lb + ub) / 2; if (rank0(mid) > i) ub = mid; else lb = mid; } return lb; } int select1(int i) const { if (i >= n - zeros) return -1; int lb = 0, ub = n; while (ub - lb > 1) { int mid = (lb + ub) / 2; if (rank1(mid) > i) ub = mid; else lb = mid; } return lb; } }; } // namespace kk2 #endif // KK2_DATA_STRUCTURE_BIT_VECTOR_HPP namespace kk2 { template <typename T> struct WaveletMatrix { int n, lg; std::vector<T> a; std::vector<BitVector> mat; bool built = false; WaveletMatrix() = default; WaveletMatrix(int n_) : n(n_) {} WaveletMatrix(const std::vector<T> &a_) : n(a_.size()), a(a_) { build(); } void build() { built = true; lg = 0; T mx = *std::max_element(a.begin(), a.end()); if (mx <= 0) mx = 1; lg = msb(mx) + 1; mat.resize(lg, BitVector(n)); std::vector<T> now(a), nxt(n); for (int i = lg - 1; i >= 0; --i) { BitVector &bv = mat[i]; for (int j = 0; j < n; ++j) { if ((now[j] >> i) & 1) bv.set(j); } bv.build(); int one = bv.zeros, zero = 0; for (int j = 0; j < n; ++j) { if ((now[j] >> i) & 1) { nxt[one++] = now[j]; } else { nxt[zero++] = now[j]; } } std::swap(now, nxt); } } void set(int i, T x) { assert(0 <= i && i < n); assert(x >= 0); assert(!built); a[i] = x; } T access(int k) const { assert(0 <= k && k < n); return a[k]; } int rank(T b, int k) { assert(0 <= k && k <= n); int l = 0, r = k; for (int i = lg - 1; i >= 0; --i) { r = (b >> i & 1) ? mat[i].rank1(r) + mat[i].zeros : mat[i].rank0(r); l = (b >> i & 1) ? mat[i].rank1(l) + mat[i].zeros : mat[i].rank0(l); } return r - l; } int select(T b, int k) { assert(0 <= k && k < n); int l = 0; for (int i = lg - 1; i >= 0; --i) l = (b >> i & 1) ? mat[i].rank1(l) + mat[i].zeros : mat[i].rank0(l); k += l; for (int i = 0; i < lg; ++i) { k = (b >> i & 1) ? mat[i].select1(k - mat[i].zeros) : mat[i].select0(k); if (k == -1) return -1; } return k; } T kth_smallest(int l, int r, int k) const { assert(0 <= l && l <= r && r <= n); assert(r - l > k); T res = 0; for (int i = lg - 1; i >= 0; --i) { int ll = mat[i].rank0(l), rr = mat[i].rank0(r); if (k < rr - ll) { l = ll, r = rr; } else { k -= rr - ll; res |= T(1) << i; l += mat[i].zeros - ll; r += mat[i].zeros - rr; } } return res; } T kth_largest(int l, int r, int k) const { assert(0 <= l && l <= r && r <= n); assert(r - l > k); return kth_smallest(l, r, r - l - k - 1); } int range_freq(int l, int r, T upper) const { assert(0 <= l && l <= r && r <= n); assert(0 <= upper); if (upper >> lg) return r - l; int res = 0; for (int i = lg - 1; i >= 0; --i) { if (upper >> i & 1) res += mat[i].rank0(r) - mat[i].rank0(l); l = (upper >> i & 1) ? mat[i].rank1(l) + mat[i].zeros : mat[i].rank0(l); r = (upper >> i & 1) ? mat[i].rank1(r) + mat[i].zeros : mat[i].rank0(r); if (l == r) break; } return res; } int range_freq(int l, int r, T lower, T upper) { assert(0 <= l && l <= r && r <= n); assert(0 <= lower && lower <= upper); return range_freq(l, r, upper) - range_freq(l, r, lower); } T max_not_greater(int l, int r, T b) { assert(0 <= l && l <= r && r <= n); int count = range_freq(l, r, b + 1); return count == 0 ? -1 : kth_smallest(l, r, count - 1); } T min_not_less(int l, int r, T b) { assert(0 <= l && l <= r && r <= n); int count = range_freq(l, r, b); return count == r - l ? -1 : kth_smallest(l, r, count); } }; } // namespace kk2 #endif // KK2_DATA_STRUCTURE_WAVELET_MATRIX_HPP #ifndef KK2_MATH_LPF_TABLE_HPP #define KK2_MATH_LPF_TABLE_HPP 1 namespace kk2 { struct LPFTable { private: static inline std::vector<int> _primes{2}, _lpf{}; public: LPFTable() = delete; static void set_upper(int m, int reserve_size = 26355867) { if ((int)_lpf.size() == 0) _primes.reserve(reserve_size); if ((int)_lpf.size() > m) return; m = std::max<int>(2 * _lpf.size(), m); _lpf.resize(m + 1); iota(_lpf.begin(), _lpf.end(), 0); for (int i = 2; i <= m; i++) { if (_lpf[i] == i and _primes.back() < i) _primes.emplace_back(i); for (const long long p : _primes) { if (p * i > m) break; if (_lpf[i] < p) break; _lpf[p * i] = p; } } } static const std::vector<int> &primes() { return _primes; } template <typename It> struct PrimeIt { It bg, ed; PrimeIt(It bg_, It ed_) : bg(bg_), ed(ed_) {} It begin() const { return bg; } It end() const { return ed; } int size() const { return ed - bg; } int operator[](int i) const { return bg[i]; } std::vector<int> to_vec() const { return std::vector<int>(bg, ed); } }; static auto primes(int n) { if (n >= (int)_lpf.size()) set_upper(n); return PrimeIt(_primes.begin(), std::upper_bound(_primes.begin(), _primes.end(), n)); } static int lpf(int n) { assert(n > 1); if (n >= (int)_lpf.size()) set_upper(n); return _lpf[n]; } static bool isprime(int n) { assert(n > 0); if (n >= (int)_lpf.size()) set_upper(n); return n != 1 and _lpf[n] == n; } }; } // namespace kk2 #endif // KK2_MATH_LPF_TABLE_HPP using namespace std; void solve() { /* 右が無限に長いとして,行動していったものを見ればよい 食べられる iff 自分以外の最大の約数がL未満 WMなど */ using lpft = kk2::LPFTable; lpft::set_upper(1e6); vc<int> a(1e6 + 1); rep (i, 2, 1e6 + 1) a[i] = i / lpft::lpf(i); kk2::WaveletMatrix<int> wm(a); int q; kin >> q; rep (q) { int l, r; kin >> l >> r; if (l == 1) { kout << 1 << "\n"; continue; } kout << wm.range_freq(l, r + 1, l) << "\n"; } } int main() { int t = 1; // kin >> t; rep (t) solve(); return 0; } // Author: kk2 // converted by https://github.com/kk2a/cpp-bundle // 2025-04-11 23:17:28