結果

問題 No.880 Yet Another Segment Tree Problem
コンテスト
ユーザー cureskol
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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";
        }
    }
}
0