結果

問題 No.880 Yet Another Segment Tree Problem
コンテスト
ユーザー nono00
提出日時 2024-06-30 08:34:24
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 829 ms / 5,000 ms
コード長 5,568 bytes
コンパイル時間 3,540 ms
コンパイル使用メモリ 283,832 KB
実行使用メモリ 19,552 KB
最終ジャッジ日時 2025-06-20 11:20:25
合計ジャッジ時間 19,711 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
#define rep(i, l, r) for (ll i = (l); i < (r); i++)
#define rrep(i, r, l) for (ll i = (r); i-- > (l);)
#define all(x) begin(x), end(x)
template <class T>
bool chmin(T& lhs, T rhs) {
    return lhs > rhs ? (lhs = rhs, true) : false;
}
template <class T>
bool chmax(T& lhs, T rhs) {
    return lhs < rhs ? (lhs = rhs, true) : false;
}
struct IOIO {
    IOIO() { std::cin.tie(0)->sync_with_stdio(0); }
} ioio;
using namespace std;
#include <bits/stdc++.h>
using namespace std;
template <class T>
ostream& operator<<(ostream& os, const vector<T>& vs) {
    os << '{';
    rep(i, 0, (int)vs.size()) os << vs[i] << (i + 1 == (int)vs.size() ? "" : ", ");
    os << '}';
    return os;
}
template <class S, class T>
ostream& operator<<(ostream& os, const pair<S, T>& p) {
    os << '(' << p.first << ", " << p.second << ')';
    return os;
}
#ifdef DEBUG
#define dump(x) cerr << "[" + string(#x) + "] " << x << endl;
#else
#define dump(...)
#endif
template <class M>
struct segment_tree_beats {
    using T = M::T;
    using F = M::F;
    int n;
    vector<T> a;
    vector<F> lz;
    segment_tree_beats(int n_): n(bit_ceil((unsigned)n_)), a(2 * n, M::e()), lz(n, M::id()) {}
    segment_tree_beats(const vector<T>& a_):
        n(bit_ceil(a_.size())), a(2 * n, M::e()), lz(n, M::id()) {
        copy(all(a_), a.begin() + n);
        rrep(i, n, 1) update(i);
    }
    void apply(int l, int r, F v) { apply(0, n, l, r, 1, v); }
    T prod(int l, int r) { return prod(0, n, l, r, 1); }
    T get(int i) { return prod(0, n, i, i + 1, 1); }
    friend ostream& operator<<(ostream& os, segment_tree_beats& s) {
        rep(i, 0, s.n) s.get(i);
        os << vector(s.a.begin() + s.n, s.a.end());
        return os;
    }
   private:
    void apply(int l, int r, int L, int R, int i, F v) {
        if (r <= L || R <= l) return;
        int m = (l + r) / 2;
        if (L <= l && r <= R) {
            eval(i, v);
        } else {
            push(i);
            apply(l, m, L, R, 2 * i, v);
            apply(m, r, L, R, 2 * i + 1, v);
            update(i);
        }
    }
    T prod(int l, int r, int L, int R, int i) {
        if (r <= L || R <= l) return M::e();
        int m = (l + r) / 2;
        if (L <= l && r <= R) {
            return a[i];
        } else {
            push(i);
            T p = M::op(prod(l, m, L, R, 2 * i), prod(m, r, L, R, 2 * i + 1));
            return p;
        }
    }
    void push(int i) {
        eval(2 * i, lz[i]);
        eval(2 * i + 1, lz[i]);
        lz[i] = M::id();
    }
    void update(int i) { a[i] = M::op(a[2 * i], a[2 * i + 1]); }
    void eval(int i, F v) {
        a[i] = M::map(v, a[i]);
        if (i < n) {
            lz[i] = M::compose(v, lz[i]);
            if (a[i].fail) {
                push(i);
                update(i);
            }
        }
    }
};
template <class U>
struct update_gcd_max_sum {
    static constexpr U update_id = numeric_limits<U>::min();
    static constexpr U gcd_id = 0;
    static constexpr U inf = U(1e9) + 5;
    struct ope {
        U a, b;
        ope(U a, U b): a(a), b(b) {}
        static ope update(U a) { return ope(a, gcd_id); }
        static ope gcd(U b) { return ope(update_id, b); }
    };
    struct info {
        info() {}
        info(U v): s(v), x(v), n(1), l(v), fail(false), same(true) {}
        U s, x, n, l;
        bool fail;
        bool same;
        friend ostream& operator<<(ostream& os, info i) {
            os << i.s;
            return os;
        }
    };
    using T = info;
    using F = ope;
    static T op(T lhs, T rhs) {
        lhs.same &= rhs.same && lhs.x == rhs.x;
        lhs.s += rhs.s;
        chmax(lhs.x, rhs.x);
        lhs.n += rhs.n;
        lhs.l = min(lcm(lhs.l, rhs.l), inf);
        return lhs;
    }
    static T e() {
        T a;
        a.s = 0;
        a.x = -inf;
        a.n = 0;
        a.l = 1;
        a.fail = false;
        return a;
    }
    static T map(F lhs, T rhs) {
        if (lhs.a != update_id) {
            rhs.x = lhs.a;
            rhs.l = lhs.a;
            rhs.s = rhs.n * lhs.a;
        }
        if (lhs.b % rhs.l == 0) return rhs;
        if (rhs.same) {
            rhs.x = rhs.l = gcd(rhs.x, lhs.b);
            rhs.s = rhs.x * rhs.n;
            return rhs;
        }
        rhs.fail = true;
        return rhs;
    }
    static F compose(F lhs, F rhs) {
        if (lhs.a != update_id) return lhs;
        return F(rhs.a, gcd(lhs.b, rhs.b));
    }
    static F id() { return F(update_id, gcd_id); }
};
int main() {
    int n, q;
    cin >> n >> q;
    using info = update_gcd_max_sum<ll>::info;
    using ope = update_gcd_max_sum<ll>::ope;
    vector<info> a(n);
    rep(i, 0, n) {
        ll v;
        cin >> v;
        a[i] = info(v);
    }
    segment_tree_beats<update_gcd_max_sum<ll>> segtree(a);
    dump(segtree);
    rep(_, 0, q) {
        int t;
        cin >> t;
        if (t == 1) {
            int l, r;
            ll x;
            cin >> l >> r >> x;
            l--;
            segtree.apply(l, r, ope::update(x));
        } else if (t == 2) {
            int l, r;
            ll x;
            cin >> l >> r >> x;
            l--;
            segtree.apply(l, r, ope::gcd(x));
        } else if (t == 3) {
            int l, r;
            cin >> l >> r;
            l--;
            cout << segtree.prod(l, r).x << '\n';
        } else {
            int l, r;
            cin >> l >> r;
            l--;
            cout << segtree.prod(l, r).s << '\n';
        }
        dump(segtree);
    }
}
0