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

• 問題: No.880 Yet Another Segment Tree Problem
• ユーザー: 👑 hitonanode
• 提出日時: 2022-09-25 00:45:27
• 言語: C++23 (gcc 12.3.0 + boost 1.83.0)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 11,175 bytes
• コンパイル時間: 763 ms
• コンパイル使用メモリ: 94,440 KB
• 最終ジャッジ日時: 2024-04-27 04:15:12
• 合計ジャッジ時間: 1,941 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

コンパイルメッセージ

segmenttree/trees/acl_range-update-gcd-range-max-sum.hpp:8:11: error: 'uint32_t' does not name a type
segmenttree/trees/acl_range-update-gcd-range-max-sum.hpp:3:1: note: 'uint32_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
segmenttree/trees/acl_range-update-gcd-range-max-sum.hpp:11:5: error: 'uint32_t' does not name a type
segmenttree/trees/acl_range-update-gcd-range-max-sum.hpp:11:5: note: 'uint32_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
segmenttree/trees/acl_range-update-gcd-range-max-sum.hpp:12:5: error: 'uint32_t' does not name a type
segmenttree/trees/acl_range-update-gcd-range-max-sum.hpp:12:5: note: 'uint32_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
segmenttree/trees/acl_range-update-gcd-range-max-sum.hpp:13:5: error: 'uint32_t' does not name a type
segmenttree/trees/acl_range-update-gcd-range-max-sum.hpp:13:5: note: 'uint32_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
segmenttree/trees/acl_range-update-gcd-range-max-sum.hpp:14:5: error: 'uint64_t' does not name a type
segmenttree/trees/acl_range-update-gcd-range-max-sum.hpp:14:5: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
segmenttree/trees/acl_range-update-gcd-range-max-sum.hpp:18:15: error: expected ')' before 'x'
segmenttree/trees/acl_range-update-gcd-range-max-sum.hpp: In constructor 'yuki880::S::S()':
segmenttree/trees/acl_range-update-gcd-range-max-sum.hpp:17:11: error: class 'yuki880::S' does not have any field named 'max'
segmenttree/trees/acl_range-update-gcd-range-max-sum.hpp:17:19: error: class 'yuki880::S' does not have any field named 'lcm'
segmenttree/trees/acl_range-update-gcd-range-max-sum.hpp:17:27: error: class 'yuki880::S' does not have any field named 'sz'
segmenttree/trees/acl_range-update-gcd-range-max-sum.hpp:17:34: error: class 'yuki880::S' does not have any field named 'sum'
segmenttree/trees/acl_range-upd

ソースコード

#line 1 "segmenttree/test/beats_gcd.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/880"
#line 2 "segmenttree/trees/acl_range-update-gcd-range-max-sum.hpp"
#include <numeric>
#line 2 "segmenttree/acl_beats.hpp"
#include <algorithm>
#include <cassert>
#include <vector>

template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S), F (*composition)(F, F),
          F (*id)()>
class segtree_beats {
    // @param n `0 <= n`
    // @return minimum non-negative `x` s.t. `n <= 2**x`
    static int ceil_pow2(int n) {
        int x = 0;
        while ((1U << x) < (unsigned int)(n)) x++;
        return x;
    }

public:
    segtree_beats() : segtree_beats(0) {}
    explicit segtree_beats(int n) : segtree_beats(std::vector<S>(n, e())) {}
    explicit segtree_beats(const std::vector<S> &v) : _n(int(v.size())) {
        log = ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(2 * size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) { update(i); }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return get_d(p);
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, get_d(l++));
            if (r & 1) smr = op(get_d(--r), smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S all_prod() { return get_d(1); }

    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, get_d(p));
        for (int i = 1; i <= log; i++) d[p >> i].fail = true;
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) d[l >> i].fail = true;
            if (((r >> i) << i) != r) d[(r - 1) >> i].fail = true;
        }
    }

    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, get_d(l)))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, get_d(l)))) {
                        sm = op(sm, get_d(l));
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, get_d(l));
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*g)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(get_d(r), sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(get_d(r), sm))) {
                        sm = op(get_d(r), sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(get_d(r), sm);
        } while ((r & -r) != r);
        return 0;
    }

protected:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;

    void update(int k) {
        push(k);
        d[k] = op(get_d(2 * k), get_d(2 * k + 1));
    }
    void all_apply(int k, const F &f) { lz[k] = composition(f, lz[k]); }
    void push(int k) {
        if (k < size) {
            all_apply(2 * k, lz[k]);
            all_apply(2 * k + 1, lz[k]);
        }
        d[k] = mapping(lz[k], d[k]);
        lz[k] = id();
    }

    const S &get_d(int k) {
        if (lz[k] != id()) push(k);
        if (d[k].fail) update(k);

        return d[k];
    }
};

namespace RangeChMinMaxAddSum {
#line 193 "segmenttree/acl_beats.hpp"

template <typename Num>
inline Num second_lowest(Num a, Num a2, Num c, Num c2) noexcept { // a < a2, c < c2
    return a == c ? std::min(a2, c2) : a2 <= c ? a2 : c2 <= a ? c2 : std::max(a, c);
}
template <typename Num>
inline Num second_highest(Num a, Num a2, Num b, Num b2) noexcept { // a > a2, b > b2
    return a == b ? std::max(a2, b2) : a2 >= b ? a2 : b2 >= a ? b2 : std::min(a, b);
}

using BNum = long long;
constexpr BNum BINF = 1LL << 61;

struct S {
    BNum lo, hi, lo2, hi2, sum;
    unsigned sz, nlo, nhi;
    bool fail;
    S() : lo(BINF), hi(-BINF), lo2(BINF), hi2(-BINF), sum(0), sz(0), nlo(0), nhi(0), fail(0) {}
    S(BNum x, unsigned sz_ = 1)
        : lo(x), hi(x), lo2(BINF), hi2(-BINF), sum(x * sz_), sz(sz_), nlo(sz_), nhi(sz_), fail(0) {}

    template <class OStream> friend OStream &operator<<(OStream &os, const S s) {
        return os << "[(" << s.lo << "x" << s.nlo << ", " << s.lo2 << ", " << s.hi2 << ", " << s.hi
                  << "x" << s.nhi << "), sz=" << s.sz << ", sum=" << s.sum << "]";
    }
};

S e() { return S(); }
S op(S l, S r) {
    if (l.lo > l.hi) return r;
    if (r.lo > r.hi) return l;
    S ret;
    ret.lo = std::min(l.lo, r.lo), ret.hi = std::max(l.hi, r.hi);
    ret.lo2 = second_lowest(l.lo, l.lo2, r.lo, r.lo2),
    ret.hi2 = second_highest(l.hi, l.hi2, r.hi, r.hi2);
    ret.sum = l.sum + r.sum, ret.sz = l.sz + r.sz;
    ret.nlo = l.nlo * (l.lo <= r.lo) + r.nlo * (r.lo <= l.lo);
    ret.nhi = l.nhi * (l.hi >= r.hi) + r.nhi * (r.hi >= l.hi);
    return ret;
}
struct F {
    BNum lb, ub, bias;
    F() : lb(-BINF), ub(BINF), bias(0) {}
    F(BNum chmax_, BNum chmin_, BNum add) : lb(chmax_), ub(chmin_), bias(add) {}
    static F chmin(BNum x) noexcept { return F(-BINF, x, BNum(0)); }
    static F chmax(BNum x) noexcept { return F(x, BINF, BNum(0)); }
    static F add(BNum x) noexcept { return F(-BINF, BINF, x); };
    bool operator!=(const F &x) const { return lb != x.lb or ub != x.ub or bias != x.bias; }
};

F composition(F fnew, F fold) {
    F ret;
    ret.lb = std::max(std::min(fold.lb + fold.bias, fnew.ub), fnew.lb) - fold.bias;
    ret.ub = std::min(std::max(fold.ub + fold.bias, fnew.lb), fnew.ub) - fold.bias;
    ret.bias = fold.bias + fnew.bias;
    return ret;
}
F id() { return F(); }
S mapping(F f, S x) {
    if (x.sz == 0) return e();
    if (x.lo == x.hi or f.lb == f.ub or f.lb >= x.hi or f.ub < x.lo)
        return S(std::min(std::max(x.lo, f.lb), f.ub) + f.bias, x.sz);
    if (x.lo2 == x.hi) {
        x.lo = x.hi2 = std::max(x.lo, f.lb) + f.bias, x.hi = x.lo2 = std::min(x.hi, f.ub) + f.bias;
        x.sum = x.lo * x.nlo + x.hi * x.nhi;
        return x;
    }
    if (f.lb < x.lo2 and f.ub > x.hi2) {
        BNum nxt_lo = std::max(x.lo, f.lb), nxt_hi = std::min(x.hi, f.ub);
        x.sum += (nxt_lo - x.lo) * x.nlo - (x.hi - nxt_hi) * x.nhi + f.bias * x.sz;
        x.lo = nxt_lo + f.bias, x.hi = nxt_hi + f.bias, x.lo2 += f.bias, x.hi2 += f.bias;
        return x;
    }
    x.fail = 1;
    return x;
}
using segtree = segtree_beats<S, op, e, F, mapping, composition, id>;
} // namespace RangeChMinMaxAddSum
#line 4 "segmenttree/trees/acl_range-update-gcd-range-max-sum.hpp"

// CUT begin
// Verified: https://yukicoder.me/submissions/611774
namespace yuki880 {
constexpr uint32_t BINF = 1 << 30;

struct S {
    uint32_t max;
    uint32_t lcm;
    uint32_t sz;
    uint64_t sum;
    bool fail;
    bool all_same;
    S() : max(0), lcm(1), sz(1), sum(0), fail(0), all_same(0) {}
    S(uint32_t x, uint32_t sz_ = 1)
        : max(x), lcm(x), sz(sz_), sum((uint64_t)x * sz_), fail(0), all_same(1) {}
};

S e() { return S(); }

S op(S l, S r) {
    if (r.sz == 0) return l;
    if (l.sz == 0) return r;
    S ret;
    ret.max = std::max(l.max, r.max);
    ret.sum = l.sum + r.sum;
    ret.lcm = (l.lcm >= BINF or r.lcm >= BINF)
                  ? BINF
                  : std::min<uint64_t>(BINF, (uint64_t)l.lcm * r.lcm / std::__gcd(l.lcm, r.lcm));
    ret.sz = l.sz + r.sz;
    if (l.all_same and r.all_same and l.max == r.max) ret.all_same = true;
    return ret;
}

struct F {
    uint32_t dogcd, reset;
    F() : dogcd(0), reset(0) {}
    F(uint32_t g, uint32_t upd) : dogcd(g), reset(upd) {}
    static F gcd(uint32_t g) noexcept { return F(g, 0); }
    static F update(uint32_t a) noexcept { return F(0, a); }
    bool operator!=(const F &x) const {
        return dogcd != x.dogcd or reset != x.reset;
    }
};

F composition(F fnew, F fold) {
    return fnew.reset ? fnew : F(std::__gcd(fnew.dogcd, fold.dogcd), fold.reset);
}

F id() { return F(); }

S mapping(F f, S x) {
    if (x.fail) return x;
    if (f.reset) x = S(f.reset, x.sz);
    if (f.dogcd) {
        if (x.all_same)
            x = S(std::__gcd(f.dogcd, x.max), x.sz);
        else if (f.dogcd and (x.lcm == BINF or f.dogcd % x.lcm))
            x.fail = true;
    }
    return x;
}
using segtree = segtree_beats<S, op, e, F, mapping, composition, id>;
} // namespace yuki880
#line 3 "segmenttree/test/beats_gcd.test.cpp"

#include <iostream>
using namespace std;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);
    uint32_t N, Q;
    cin >> N >> Q;
    vector<yuki880::S> A(N);
    for (auto &a : A) {
        uint32_t tmp;
        cin >> tmp, a = {tmp, 1};
    }

    yuki880::segtree segtree(A);
    uint32_t q, l, r, x;
    while (Q--) {
        cin >> q >> l >> r;
        l--;
        if (q <= 2) {
            cin >> x;
            if (q == 1) segtree.apply(l, r, yuki880::F::update(x));
            if (q == 2) segtree.apply(l, r, yuki880::F::gcd(x));
        } else {
            auto v = segtree.prod(l, r);
            if (q == 3) cout << v.max << '\n';
            if (q == 4) cout << v.sum << '\n';
        }
    }
}