library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub gyouzasushi/library

:heavy_check_mark: test/library-checker/range_chmin_chmax_add_range_sum.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/range_chmin_chmax_add_range_sum"
#include <iostream>

#include "algebra/range_chmin_chmax_add_range_sum.hpp"
#include "datastructure/segtree_beats.hpp"
int main() {
    using A = range_chmin_chmax_add_range_sum<long long>;
    int n, q;
    std::cin >> n >> q;
    std::vector<A::S> a(n);
    for (auto& x : a) {
        long long v;
        std::cin >> v;
        x = A::from(v);
    }
    segtree_beats<A> seg(a);
    while (q--) {
        int t, l, r;
        std::cin >> t >> l >> r;
        if (t == 3) {
            std::cout << seg.prod(l, r).sum << '\n';
            continue;
        }
        long long b;
        std::cin >> b;
        if (t == 0) seg.apply(l, r, A::chmin(b));
        if (t == 1) seg.apply(l, r, A::chmax(b));
        if (t == 2) seg.apply(l, r, A::add(b));
    }
}
#line 1 "test/library-checker/range_chmin_chmax_add_range_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/range_chmin_chmax_add_range_sum"
#include <iostream>

#line 2 "algebra/range_chmin_chmax_add_range_sum.hpp"
#include <algorithm>
#include <limits>
template <class T>
struct range_chmin_chmax_add_range_sum {
    struct S {
        T sum, min, max, min2, max2;
        int minc, maxc, len;
        bool fail;
    };
    struct F {
        T add, chmin, chmax;
    };
    static S op(S a, S b) {
        if (a.len == 0) return b;
        if (b.len == 0) return a;
        S c;
        c.sum = a.sum + b.sum;
        c.len = a.len + b.len;
        c.fail = false;
        if (a.max > b.max) {
            c.max = a.max;
            c.maxc = a.maxc;
            c.max2 = std::max(a.max2, b.max);
        } else if (a.max < b.max) {
            c.max = b.max;
            c.maxc = b.maxc;
            c.max2 = std::max(a.max, b.max2);
        } else {
            c.max = a.max;
            c.maxc = a.maxc + b.maxc;
            c.max2 = std::max(a.max2, b.max2);
        }
        if (a.min < b.min) {
            c.min = a.min;
            c.minc = a.minc;
            c.min2 = std::min(a.min2, b.min);
        } else if (a.min > b.min) {
            c.min = b.min;
            c.minc = b.minc;
            c.min2 = std::min(a.min, b.min2);
        } else {
            c.min = a.min;
            c.minc = a.minc + b.minc;
            c.min2 = std::min(a.min2, b.min2);
        }
        return c;
    }
    static S e() {
        return {T(0), inf, ninf, inf, ninf, 0, 0, 0, false};
    }
    static S mapping(F f, S x) {
        if (x.len == 0) return x;
        if (f.add != T(0)) {
            x.sum += f.add * x.len;
            x.min += f.add;
            x.max += f.add;
            if (x.min2 != inf) x.min2 += f.add;
            if (x.max2 != ninf) x.max2 += f.add;
        }
        if (f.chmin < x.max) {
            if (f.chmin <= x.min) {
                fill(x, f.chmin);
            } else if (x.max2 < f.chmin) {
                x.sum += (f.chmin - x.max) * x.maxc;
                if (x.min2 == x.max) x.min2 = f.chmin;
                x.max = f.chmin;
            } else {
                x.fail = true;
                return x;
            }
        }
        if (f.chmax > x.min) {
            if (f.chmax >= x.max) {
                fill(x, f.chmax);
            } else if (f.chmax < x.min2) {
                x.sum += (f.chmax - x.min) * x.minc;
                if (x.max2 == x.min) x.max2 = f.chmax;
                x.min = f.chmax;
            } else {
                x.fail = true;
            }
        }
        return x;
    }
    static F composition(F f, F g) {
        T chmin = g.chmin == inf ? inf : g.chmin + f.add;
        T chmax = g.chmax == ninf ? ninf : g.chmax + f.add;
        return {f.add + g.add, std::min(chmin, f.chmin), std::max(std::min(chmax, f.chmin), f.chmax)};
    }
    static F id() {
        return {T(0), inf, ninf};
    }
    static constexpr bool composition_commutative = false;
    static S from(T v) {
        return {v, v, v, inf, ninf, 1, 1, 1, false};
    }
    static F chmin(T x) {
        return {T(0), x, ninf};
    }
    static F chmax(T x) {
        return {T(0), inf, x};
    }
    static F add(T x) {
        return {x, inf, ninf};
    }
    static F assign(T x) {
        return {T(0), x, x};
    }

private:
    static constexpr T inf = std::numeric_limits<T>::max();
    static constexpr T ninf = std::numeric_limits<T>::lowest();
    static void fill(S& x, T v) {
        x.sum = v * x.len;
        x.min = x.max = v;
        x.min2 = inf;
        x.max2 = ninf;
        x.minc = x.maxc = x.len;
    }
};
#line 2 "datastructure/segtree_beats.hpp"
#include <bit>
#include <cassert>
#include <vector>

#line 2 "algebra/concept.hpp"
#include <concepts>
template <class M>
concept semigroup = requires(typename M::S a, typename M::S b) {
    { M::op(a, b) } -> std::same_as<typename M::S>;
};
template <class M>
concept monoid = semigroup<M> && requires {
    { M::e() } -> std::same_as<typename M::S>;
};
template <class G>
concept group = monoid<G> && requires(typename G::S a) {
    { G::inv(a) } -> std::same_as<typename G::S>;
};
template <class A>
concept action = requires(typename A::F f, typename A::F g) {
    { A::composition(f, g) } -> std::same_as<typename A::F>;
    { A::id() } -> std::same_as<typename A::F>;
    { A::composition_commutative } -> std::convertible_to<bool>;
};
template <class A>
concept acted_monoid = monoid<A> && action<A> && requires(typename A::S x, typename A::F f) {
    { A::mapping(f, x) } -> std::same_as<typename A::S>;
};
template <class R>
concept semiring = requires(typename R::S a, typename R::S b) {
    { R::add(a, b) } -> std::same_as<typename R::S>;
    { R::zero() } -> std::same_as<typename R::S>;
    { R::mul(a, b) } -> std::same_as<typename R::S>;
    { R::one() } -> std::same_as<typename R::S>;
};
template <class A>
concept beats_acted_monoid = acted_monoid<A> && requires(typename A::S x) {
    { x.fail } -> std::convertible_to<bool>;
};
#line 7 "datastructure/segtree_beats.hpp"
template <beats_acted_monoid A> struct segtree_beats {
public:
    using S = typename A::S;
    using F = typename A::F;
    segtree_beats() : segtree_beats(0) {
    }
    explicit segtree_beats(int n) : segtree_beats(std::vector<S>(n, A::e())) {
    }
    explicit segtree_beats(const std::vector<S>& v) : _n(int(v.size())) {
        size = int(std::bit_ceil(unsigned(_n)));
        log = std::countr_zero(unsigned(size));
        d = std::vector<S>(2 * size, A::e());
        lz = std::vector<F>(size, A::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 d[p];
    }
    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return A::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 = A::e(), smr = A::e();
        while (l < r) {
            if (l & 1) sml = A::op(sml, d[l++]);
            if (r & 1) smr = A::op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return A::op(sml, smr);
    }
    S all_prod() const {
        return 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] = A::mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    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) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }
    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(A::e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = A::e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(A::op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(A::op(sm, d[l]))) {
                        sm = A::op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = A::op(sm, 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(A::e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = A::e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(A::op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(A::op(d[r], sm))) {
                        sm = A::op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = A::op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;
    void update(int k) {
        d[k] = A::op(d[2 * k], d[2 * k + 1]);
    }
    void all_apply(int k, F f) {
        d[k] = A::mapping(f, d[k]);
        if (k < size) {
            lz[k] = A::composition(f, lz[k]);
            if (d[k].fail) {
                push(k);
                update(k);
            }
        }
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = A::id();
    }
};
#line 6 "test/library-checker/range_chmin_chmax_add_range_sum.test.cpp"
int main() {
    using A = range_chmin_chmax_add_range_sum<long long>;
    int n, q;
    std::cin >> n >> q;
    std::vector<A::S> a(n);
    for (auto& x : a) {
        long long v;
        std::cin >> v;
        x = A::from(v);
    }
    segtree_beats<A> seg(a);
    while (q--) {
        int t, l, r;
        std::cin >> t >> l >> r;
        if (t == 3) {
            std::cout << seg.prod(l, r).sum << '\n';
            continue;
        }
        long long b;
        std::cin >> b;
        if (t == 0) seg.apply(l, r, A::chmin(b));
        if (t == 1) seg.apply(l, r, A::chmax(b));
        if (t == 2) seg.apply(l, r, A::add(b));
    }
}
Back to top page