#1144566 (C++23) No.880 Yet Another Segment Tree Problem

• 問題: No.880 Yet Another Segment Tree Problem
• ユーザー: vjudge1
• 提出日時: 2026-01-12 15:37:04
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 7,978 bytes
• コンパイル時間: 2,561 ms
• コンパイル使用メモリ: 231,740 KB
• 実行使用メモリ: 16,200 KB
• 最終ジャッジ日時: 2026-01-12 15:37:58
• 合計ジャッジ時間: 53,427 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

ファイルパターン	結果
sample	AC * 1
other	AC * 31 TLE * 1 -- * 6

ソースコード

#include <vector>
#include <algorithm>
#include <type_traits>
#include <cassert>

template<typename S, typename F,
        S (*op)(const S&, const S&)=S::unite,
        S (*mapping)(const F&, const S&)=F::apply,
        F (*composition)(const F&, const F&)=F::unite
>
struct LazySeg {
    int n, M, lg;
    std::vector<S> d;
    std::vector<F> lz;

    std::vector<int> _points, _rps;

    explicit LazySeg(int n_) : LazySeg(std::vector<S>(n_)) {}

    explicit LazySeg(const std::vector<S> &v) : LazySeg(v.begin(), v.end()) { }

    template<typename ForwardIt, typename std::enable_if<std::is_same<S, typename std::iterator_traits<ForwardIt>::value_type>::value, bool>::type = true>
    explicit LazySeg(ForwardIt first, ForwardIt last) {
        n = std::distance(first, last);
//        lg = 0; M = 1;
//        while (M < n) lg++, M<<=1;
        M = n;
        lg = 31 - __builtin_clz(n);
        d = std::vector<S>(2 * M);
        lz = std::vector<F>(M);
        for (int i = 0; i < n; i++) {
            d[M + i] = *first;
            ++first;
        }
        for (int i = M - 1; i >= 1; i--)
            pull(i);
    }

    S get(int x) {
        assert(0 <= x && x < n);
        x += M;
        for (int i=lg; i>=1; i--) push(x >> i);
        return d[x];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= n);
        if (l == r) return S();
        range_push(l, r);
        S sml{}, smr{};
        for (l += M, r += M; l < r; l >>= 1, r >>= 1) {
            if (l&1) sml = op(sml, d[l++]);
            if (r&1) smr = op(d[--r], smr);
        }
        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    void set(int x, S v) {
        assert(0 <= x && x < n);
        x += M;
        for (int i=lg; i>=1; i--) push(x >> i);
        d[x] = v;
        for (int i=1; i<=lg; i++) pull(x >> i);
    }

    void apply(int x, const F& f) {
        assert(0 <= x && x < n);
        x += M;
        for (int i = lg; i >= 1; i--) push(x >> i);
        d[x] = mapping(f, d[x]);
        for (int i = 1; i <= lg; i++) pull(x >> i);
    }

    void apply(int l, int r, const F& f) {
        assert(0 <= l && l <= r && r <= n);
        if (l == r) return;

        range_push(l, r); l += M; r += M;

        for (int s=l, t=r; s < t; s>>=1, t>>=1) {
            if (s & 1) apply_f(s++, f);
            if (t & 1) apply_f(--t, f);
        }

        for (int i = 1; i <= lg; i++) {
            if (((l >> i) << i) != l) pull(l >> i);
            if (((r >> i) << i) != r) pull((r - 1) >> i);
        }
    }

    // find minimal position R (l <= R < r) that g(prod(l, R+1)) == true
    // forall l <= i <= R, g(prod(l, i)) == false
    // if not found, return r
    template<typename G>
    int find_first(int l, int r, G g) {
        assert(0 <= l && r <= n && l <= r);
        _prepare_points(l, r);
        range_push(l, r);
        S acc{};
        for (int x : _points) {
            S candidate = op(acc, d[x]);
            if (g(candidate)) {
                while (x < M) {
                    push(x);
                    x <<= 1;
                    S c2 = op(acc, d[x]);
                    if (!g(c2)) {
                        acc = c2; x++;
                    }
                }
                return x - M;
            }
            acc = candidate;
        }
        return r;
    }

    template<typename G> int find_first(int l, G g) { return find_first(l, n, g); }

    // find minimal position L that g(prod(L, r)) == true
    // forall l <= i < L, g(prod(i, r)) == false
    template <class G> int find_last(int l, int r, G g) {
        assert(0 <= l && r <= n && l <= r);
        _prepare_points(l, r, true);
        range_push(l, r);
        S acc{};
        for (int x : _points) {
            S candidate = op(d[x], acc);
            if (!g(candidate)) {
                while (x < M) {
                    push(x);
                    x = (x * 2 + 1);
                    S c2 = op(d[x], acc);
                    if (g(c2)) {
                        acc = c2; x--;
                    }
                }
                return x + 1 - M;
            }
            acc = candidate;
        }
        return l;
    }

    template <class G> int find_last(int r, G g) { return find_last(0, r, g); }

private:

    void _prepare_points(int l, int r, bool reversed=false) {
        _points.clear(); _rps.clear();
        for (l += M, r += M; l < r; l >>= 1, r >>= 1) {
            if (l & 1) _points.push_back(l++);
            if (r & 1) _rps.push_back(--r);
        }
        if (reversed) {
            _rps.insert(_rps.end(), _points.rbegin(), _points.rend());
            swap(_points, _rps);
        } else {
            _points.insert(_points.end(), _rps.rbegin(), _rps.rend());
        }
    }

    void range_push(int l, int r) {
        l += M; r += M;
        for (int i=lg; i>=1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r-1) >> i);
        }
    }

    void pull(int x) {
        d[x] = op(d[x << 1], d[x<<1|1]);
    }

    void apply_f(int x, F f) {
        d[x] = mapping(f, d[x]);
        if (x < M) {
            lz[x] = composition(f, lz[x]);
            if (d[x].fail) {
                push(x);
                pull(x);
            }
        }
    }

    void push(int x) {
        if (!x) return;
        apply_f(x<<1, lz[x]);
        apply_f(x<<1|1, lz[x]);
        lz[x] = F();
    }
};

#include <stdio.h>
#include <assert.h>
#include <math.h>
#include <cstdint>
#include <algorithm>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <queue>
#include <iostream>
#include <iomanip>
#include <string>
#include <bitset>
#include <functional>
#include <string.h>
#include <numeric>

using namespace std;

typedef long long ll;
using i64 = int64_t;
using i128 = __int128_t;
using f64 = double;

const int maxn = 200050;
const ll inf = 1e9 + 1e5;

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a%b);
}

ll safe_lcm(ll a, ll b) {
    if (a >= inf || b >= inf) return inf;
    ll g = gcd(a, b);
    ll m = a / g * b;
    if (m >= inf) return inf;
    return m;
}

struct node {

    ll s = 0;
    ll g = 0;
    int mx = 0;
    int sz = 0;
    bool fail = false;

    node() {}
    node(ll s, ll g, int mx, int sz) : s(s), g(g), mx(mx), sz(sz), fail(false) { }

    static node unite(const node &a, const node &b) {
        return {a.s + b.s, safe_lcm(a.g, b.g), max(a.mx, b.mx), a.sz + b.sz};
    }
};

struct fnode {

    int x = 0;
    int y = -1;

    fnode() {}
    fnode(ll x, int y) : x(x), y(y) { }

    static node apply(const fnode &f, const node &s) {
        node c = s;
        if (f.y != -1) {
            ll w = gcd(f.x, f.y);
            c.s = w * c.sz;
            c.g = w;
            c.mx = w;
        } else {
            if (c.sz == 1) {
                ll w = gcd(f.x, c.g);
                c.mx = c.g = c.s = w;
            } else if (c.g == inf || f.x % c.g) {
                c.fail = true;
            }
        }
        return c;
    }

    static fnode unite(const fnode &f, const fnode &g) {
        // if (f.x && g.x) cout << "fuck\n";
        if (f.y != -1) return f;
        return {gcd(f.x, g.x), g.y};
    }
};



int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << fixed << setprecision(20);

    int n, Q;
    cin >> n >> Q;
    vector<node> data(n);
    for (int i=0; i<n; i++) {
        int x;
        cin >> x;
        data[i].s = data[i].g = data[i].mx = x;
        data[i].sz = 1;
    }
    LazySeg<node, fnode> tree(data);
    while (Q--) {
        int op, l, r, x;
        cin >> op >> l >> r;
        --l;
        if (op <= 2) cin >> x;
        if (op == 1) {
            tree.apply(l, r, {0, x});
        } else if (op == 2) {
            tree.apply(l, r, {x, -1});
        } else if (op == 3) {
            cout << tree.prod(l, r).mx << '\n';
        } else {
            cout << tree.prod(l, r).s << '\n';
        }
    }
}