結果
問題 |
No.880 Yet Another Segment Tree Problem
|
ユーザー |
![]() |
提出日時 | 2025-07-01 11:25:16 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 515 ms / 5,000 ms |
コード長 | 5,796 bytes |
コンパイル時間 | 4,365 ms |
コンパイル使用メモリ | 302,164 KB |
実行使用メモリ | 18,432 KB |
最終ジャッジ日時 | 2025-07-01 11:25:35 |
合計ジャッジ時間 | 16,954 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h> template <typename Monoid> struct SegmentTree { using S = typename Monoid::value_type; const size_t N; std::vector<S> data; void update(size_t v) { data[v] = Monoid::op(data[v << 1 | 0], data[v << 1 | 1]); } std::vector<size_t> range_vertices(size_t l, size_t r) const { std::vector<size_t> L, R; for (l += N, r += N; l < r; l >>= 1, r >>= 1) { if (l & 1) L.push_back(l++); if (r & 1) R.push_back(--r); } std::ranges::copy(std::ranges::reverse_view(R), std::back_inserter(L)); return L; } SegmentTree(const std::vector<S> &a) : N(std::bit_ceil(a.size())), data(2 * N) { std::ranges::copy(a, &data[N]); for (int i = N - 1; i; i--) update(i); } void set(size_t i, int x) { i += N; data[i] = x; for (i >>= 1; i; i >>= 1) update(i); } S prod(size_t l, size_t r) const { S ret = Monoid::e(); for (size_t v : range_vertices(l, r)) ret = Monoid::op(ret, data[v]); return ret; } }; template <typename Lazy> struct LazySegmentTree : public SegmentTree<typename Lazy::Monoid> { using S = typename Lazy::Monoid::value_type; using F = typename Lazy::Function::value_type; using segtree = SegmentTree<typename Lazy::Monoid>; using segtree::data; using segtree::N; std::vector<F> lazy; virtual void apply_vertex(size_t v, const F &f) { data[v] = Lazy::mapping(f, data[v]); if (v < N) lazy[v] = Lazy::Function::op(f, lazy[v]); } void push(size_t v) { for (int b : {0, 1}) apply_vertex(v << 1 | b, lazy[v]); lazy[v] = Lazy::Function::e(); } std::vector<size_t> range_ancestors(size_t l, size_t r) const { l += N, r += N; std::vector<size_t> ret; for (int lg = 0; lg < std::bit_width(N); lg++) { if (std::countr_zero(l) < lg) ret.push_back(l >> lg); if (std::countr_zero(r) < lg) ret.push_back((r - 1) >> lg); } return ret; } void range_push(size_t l, size_t r) { for (size_t v : std::ranges::reverse_view(range_ancestors(l, r))) push(v); } LazySegmentTree(const std::vector<S> &a) : segtree::SegmentTree(a), lazy(N, Lazy::Function::e()) {} void apply(size_t l, size_t r, const F &f) { range_push(l, r); for (size_t v : segtree::range_vertices(l, r)) apply_vertex(v, f); for (size_t v : range_ancestors(l, r)) segtree::update(v); } S prod(size_t l, size_t r) { range_push(l, r); return segtree::prod(l, r); } }; template <typename LazyBeats> struct SegmentTreeBeats : public LazySegmentTree<LazyBeats> { using Base = LazySegmentTree<LazyBeats>; using Base::Base; void apply_vertex(size_t v, const Base::F &f) override { Base::apply_vertex(v, f); if (LazyBeats::is_fail) { Base::push(v); Base::segtree::update(v); } } }; using ll = long long; static constexpr ll inf = ll(1e9) + 1; struct MaxSum { struct S { int max; ll sum; int size; ll lcm; bool all_same; }; using value_type = S; static S op(const S &a, const S &b) { return S(std::max(a.max, b.max), a.sum + b.sum, a.size + b.size, std::min(std::lcm(a.lcm, b.lcm), inf), a.all_same and b.all_same and a.max == b.max); } static S e() { return S(0, 0, 0, 1, true); } }; struct AssignGcd { struct S { bool is_assign; int val; }; using value_type = S; static S op(const S &a, const S &b) { if (a.is_assign) return a; if (b.is_assign) return S(true, std::gcd(a.val, b.val)); return S(false, std::gcd(a.val, b.val)); } static S e() { return S(false, 0); } }; struct RangeAssignGcdRangeMaxSum { using Monoid = MaxSum; using Function = AssignGcd; using S = Monoid::value_type; using F = Function::value_type; inline static bool is_fail; static S mapping(const F &f, const S &x) { if (f.is_assign and f.val == 0) { // std::cerr << "A" << std::endl; exit(0); } if (x.lcm == 0) { // std::cerr << x.lcm << " " << x.max << " " << x.size << " " // << x.all_same << std::endl; return x; } is_fail = false; if (f.is_assign) return S(f.val, ll(f.val) * x.size, x.size, f.val, true); if (f.val % x.lcm == 0) return x; if (x.all_same) return S(std::gcd(x.max, f.val), std::gcd(x.max, f.val) * ll(x.size), x.size, std::max(1, std::gcd(x.max, f.val)), true); is_fail = true; return S(); } }; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q; std::cin >> n >> q; std::vector<MaxSum::S> v(n); for (auto &x : v) { int a; std::cin >> a; x = MaxSum::S(a, a, 1, a, true); } SegmentTreeBeats<RangeAssignGcdRangeMaxSum> beats(v); while (q--) { int t, l, r; std::cin >> t >> l >> r; l--; if (t <= 2) { int x; std::cin >> x; beats.apply(l, r, AssignGcd::S(t == 1, x)); } else { auto res = beats.prod(l, r); if (t == 3) std::cout << res.max << "\n"; else std::cout << res.sum << "\n"; } } }