結果
問題 | No.880 Yet Another Segment Tree Problem |
ユーザー |
|
提出日時 | 2022-06-19 18:49:41 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 11,978 bytes |
コンパイル時間 | 941 ms |
コンパイル使用メモリ | 83,028 KB |
最終ジャッジ日時 | 2025-01-29 23:24:12 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 36 TLE * 1 |
ソースコード
#define PROBLEM "https://yukicoder.me/problems/no/880"#include <iostream>#include <numeric>#include <cassert>#include <vector>#include <limits>#include <type_traits>namespace suisen {// ! utilitytemplate <typename ...Types>using constraints_t = std::enable_if_t<std::conjunction_v<Types...>, std::nullptr_t>;template <bool cond_v, typename Then, typename OrElse>constexpr decltype(auto) constexpr_if(Then&& then, OrElse&& or_else) {if constexpr (cond_v) {return std::forward<Then>(then);} else {return std::forward<OrElse>(or_else);}}// ! functiontemplate <typename ReturnType, typename Callable, typename ...Args>using is_same_as_invoke_result = std::is_same<std::invoke_result_t<Callable, Args...>, ReturnType>;template <typename F, typename T>using is_uni_op = is_same_as_invoke_result<T, F, T>;template <typename F, typename T>using is_bin_op = is_same_as_invoke_result<T, F, T, T>;template <typename Comparator, typename T>using is_comparator = std::is_same<std::invoke_result_t<Comparator, T, T>, bool>;// ! integraltemplate <typename T, typename = constraints_t<std::is_integral<T>>>constexpr int bit_num = std::numeric_limits<std::make_unsigned_t<T>>::digits;template <typename T, unsigned int n>struct is_nbit { static constexpr bool value = bit_num<T> == n; };template <typename T, unsigned int n>static constexpr bool is_nbit_v = is_nbit<T, n>::value;// ?template <typename T>struct safely_multipliable {};template <>struct safely_multipliable<int> { using type = long long; };template <>struct safely_multipliable<long long> { using type = __int128_t; };template <>struct safely_multipliable<unsigned int> { using type = unsigned long long; };template <>struct safely_multipliable<unsigned long int> { using type = __uint128_t; };template <>struct safely_multipliable<unsigned long long> { using type = __uint128_t; };template <>struct safely_multipliable<float> { using type = float; };template <>struct safely_multipliable<double> { using type = double; };template <>struct safely_multipliable<long double> { using type = long double; };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;} // namespace suisennamespace suisen {template <typename T, typename UpdateFunc, constraints_t<std::is_invocable<UpdateFunc>> = nullptr>struct UpdateProxyObject {public:UpdateProxyObject(T &v, UpdateFunc update) : v(v), update(update) {}operator T() const { return v; }auto& operator++() && { ++v, update(); return *this; }auto& operator--() && { --v, update(); return *this; }auto& operator+=(const T &val) && { v += val, update(); return *this; }auto& operator-=(const T &val) && { v -= val, update(); return *this; }auto& operator*=(const T &val) && { v *= val, update(); return *this; }auto& operator/=(const T &val) && { v /= val, update(); return *this; }auto& operator%=(const T &val) && { v %= val, update(); return *this; }auto& operator =(const T &val) && { v = val, update(); return *this; }auto& operator<<=(const T &val) && { v <<= val, update(); return *this; }auto& operator>>=(const T &val) && { v >>= val, update(); return *this; }template <typename F, constraints_t<is_uni_op<F, T>> = nullptr>auto& apply(F f) && { v = f(v), update(); return *this; }private:T &v;UpdateFunc update;};} // namespace suisennamespace suisen {template <typename T, T(*op)(T, T), T(*e)(), typename F, T(*mapping)(F, T), F(*composition)(F, F), F(*id)(), bool enable_beats = false>struct LazySegmentTree {using value_type = T;using operator_type = F;LazySegmentTree() : LazySegmentTree(0) {}LazySegmentTree(int n) : LazySegmentTree(std::vector<value_type>(n, e())) {}LazySegmentTree(const std::vector<value_type>& init) : n(init.size()), m(ceil_pow2(n)), lg(__builtin_ctz(m)), data(2 * m, e()), lazy(m, id()){std::copy(init.begin(), init.end(), data.begin() + m);for (int k = m - 1; k > 0; --k) update(k);}void apply(int l, int r, const operator_type& f) {assert(0 <= l and l <= r and r <= n);push_to(l, r);for (int l2 = l + m, r2 = r + m; l2 < r2; l2 >>= 1, r2 >>= 1) {if (l2 & 1) all_apply(l2++, f);if (r2 & 1) all_apply(--r2, f);}update_from(l, r);}void apply(int p, const operator_type& f) {(*this)[p] = mapping(f, get(p));}value_type operator()(int l, int r) {assert(0 <= l and l <= r and r <= n);push_to(l, r);value_type res_l = e(), res_r = e();for (l += m, r += m; l < r; l >>= 1, r >>= 1) {if (l & 1) res_l = op(res_l, data[l++]);if (r & 1) res_r = op(data[--r], res_r);}return op(res_l, res_r);}value_type prod(int l, int r) { return (*this)(l, r); }value_type prefix_prod(int r) { return (*this)(0, r); }value_type suffix_prod(int l) { return (*this)(l, m); }value_type all_prod() const { return data[1]; }auto operator[](int p) {assert(0 <= p and p < n);push_to(p);return UpdateProxyObject{ data[p + m], [this, p] { update_from(p); } };}value_type get(int p) { return (*this)[p]; }void set(int p, value_type v) { (*this)[p] = v; }template <typename Pred, constraints_t<is_same_as_invoke_result<bool, Pred, value_type>> = nullptr>int max_right(int l, Pred g) {assert(0 <= l && l <= n);assert(g(e()));if (l == n) return n;l += m;for (int i = lg; i >= 1; --i) push(l >> i);value_type sum = e();do {while ((l & 1) == 0) l >>= 1;if (not g(op(sum, data[l]))) {while (l < m) {push(l);l = 2 * l;if (g(op(sum, data[l]))) sum = op(sum, data[l++]);}return l - m;}sum = op(sum, data[l++]);} while ((l & -l) != l);return n;}template <bool(*f)(value_type)>int max_right(int l) { return max_right(l, f); }template <typename Pred, constraints_t<is_same_as_invoke_result<bool, Pred, value_type>> = nullptr>int min_left(int r, Pred g) {assert(0 <= r && r <= n);assert(g(e()));if (r == 0) return 0;r += m;for (int i = lg; i >= 1; --i) push(r >> i);value_type sum = e();do {r--;while (r > 1 and (r & 1)) r >>= 1;if (not g(op(data[r], sum))) {while (r < m) {push(r);r = 2 * r + 1;if (g(op(data[r], sum))) sum = op(data[r--], sum);}return r + 1 - m;}sum = op(data[r], sum);} while ((r & -r) != r);return 0;}template <bool(*f)(value_type)>int min_left(int l) { return min_left(l, f); }private:int n, m, lg;std::vector<value_type> data;std::vector<operator_type> lazy;static constexpr int ceil_pow2(int n) {int m = 1;while (m < n) m <<= 1;return m;}void all_apply(int k, const operator_type& f) {data[k] = mapping(f, data[k]);if (k < m) {lazy[k] = composition(f, lazy[k]);if constexpr (enable_beats) if (data[k].fail) push(k), update(k);}}void push(int k) {all_apply(2 * k, lazy[k]), all_apply(2 * k + 1, lazy[k]);lazy[k] = id();}void push_to(int p) {p += m;for (int i = lg; i >= 1; --i) push(p >> i);}void push_to(int l, int r) {l += m, r += m;int li = __builtin_ctz(l), ri = __builtin_ctz(r);for (int i = lg; i >= li + 1; --i) push(l >> i);for (int i = lg; i >= ri + 1; --i) push(r >> i);}void update(int k) {data[k] = op(data[2 * k], data[2 * k + 1]);}void update_from(int p) {p += m;for (int i = 1; i <= lg; ++i) update(p >> i);}void update_from(int l, int r) {l += m, r += m;int li = __builtin_ctz(l), ri = __builtin_ctz(r);for (int i = li + 1; i <= lg; ++i) update(l >> i);for (int i = ri + 1; i <= lg; ++i) update(r >> i);}};}namespace suisen {template <typename T, T(*op)(T, T), T(*e)(), typename F, T(*mapping)(F, T), F(*composition)(F, F), F(*id)()>using SegmentTreeBeats = LazySegmentTree<T, op, e, F, mapping, composition, id, /* enable_beats = */ true>;} // namespace suisenconstexpr long long inf = 2000000000;struct S {long long sum_v;int max_v;long long lcm_v;int siz;bool fail = false;S(long long sum_v, int max_v, long long lcm_v, int siz) : sum_v(sum_v), max_v(max_v), lcm_v(lcm_v), siz(siz) {}S(int v) : sum_v(v), max_v(v), lcm_v(v), siz(1) {}S() = default;};struct F {int upd_v = 0;int gcd_v = 0;F(int upd_v = 0, int gcd_v = 0) : upd_v(upd_v), gcd_v(gcd_v) {}static F upd_query(int upd_v) {return F { upd_v, 0 };}static F gcd_query(int gcd_v) {return F { 0, gcd_v };}};S op(S x, S y) {return S { x.sum_v + y.sum_v, std::max(x.max_v, y.max_v), std::min(std::lcm(x.lcm_v, y.lcm_v), inf), x.siz + y.siz };}S e() {return S { 0LL, 0, 1, 0 };}S mapping(F f, S x) {if (f.upd_v) return S { (long long) f.upd_v * x.siz, f.upd_v , f.upd_v, x.siz };if (f.gcd_v) {if (x.siz == 1) {return S { std::gcd(x.max_v, f.gcd_v) };} else if (f.gcd_v % x.lcm_v) {x.fail = true;}}return x;}F composition(F f, F g) {if (f.upd_v) return f;if (g.upd_v) return F::upd_query(std::gcd(g.upd_v, f.gcd_v));return F::gcd_query(std::gcd(f.gcd_v, g.gcd_v));}F id() {return F::gcd_query(0);}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n, q;std::cin >> n >> q;std::vector<S> init(n);for (int i = 0; i < n; ++i) {int v;std::cin >> v;init[i] = S{v};}suisen::SegmentTreeBeats<S, op, e, F, mapping, composition, id> seg(init);while (q --> 0) {int qt;std::cin >> qt;if (qt == 1) {int l, r, x;std::cin >> l >> r >> x;--l;seg.apply(l, r, F::upd_query(x));} else if (qt == 2) {int l, r, x;std::cin >> l >> r >> x;--l;seg.apply(l, r, F::gcd_query(x));} else if (qt == 3) {int l, r;std::cin >> l >> r;--l;std::cout << seg.prod(l, r).max_v << '\n';} else {int l, r;std::cin >> l >> r;--l;std::cout << seg.prod(l, r).sum_v << '\n';}}return 0;}