test/aoj/DSL_2_G.test.cpp

View this file on GitHub
Last update: 2026-10-26 01:30:50+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_G

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_G"
#include <iostream>
#include <vector>

#include "algebra/range_add_range_sum.hpp"
#include "datastructure/lazy_segtree.hpp"
int main() {
    int n, q;
    std::cin >> n >> q;
    using A = range_add_range_sum<long long>;
    lazy_segtree<A> seg(std::vector<A::S>(n, A::from(0)));
    while (q--) {
        int t;
        std::cin >> t;
        if (t == 0) {
            int s, e;
            long long x;
            std::cin >> s >> e >> x;
            seg.apply(s - 1, e, x);
        } else {
            int s, e;
            std::cin >> s >> e;
            std::cout << seg.prod(s - 1, e).sum << '\n';
        }
    }
}

#line 1 "test/aoj/DSL_2_G.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_G"
#include <iostream>
#include <vector>

#line 2 "algebra/range_add_range_sum.hpp"
template <class T>
struct range_add_range_sum {
    struct S {
        T sum;
        int len;
    };
    using F = T;
    static S op(S a, S b) {
        return {a.sum + b.sum, a.len + b.len};
    }
    static S e() {
        return {T(0), 0};
    }
    static S mapping(F f, S x) {
        return {x.sum + f * x.len, x.len};
    }
    static F composition(F f, F g) {
        return f + g;
    }
    static F id() {
        return T(0);
    }
    static constexpr bool composition_commutative = true;
    static S from(T v) {
        return {v, 1};
    }
};
#line 2 "datastructure/lazy_segtree.hpp"
#include <atcoder/lazysegtree>

#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>;
};
#line 5 "datastructure/lazy_segtree.hpp"
template <acted_monoid A>
using lazy_segtree = atcoder::lazy_segtree<typename A::S, A::op, A::e, typename A::F, A::mapping, A::composition, A::id>;
#line 7 "test/aoj/DSL_2_G.test.cpp"
int main() {
    int n, q;
    std::cin >> n >> q;
    using A = range_add_range_sum<long long>;
    lazy_segtree<A> seg(std::vector<A::S>(n, A::from(0)));
    while (q--) {
        int t;
        std::cin >> t;
        if (t == 0) {
            int s, e;
            long long x;
            std::cin >> s >> e >> x;
            seg.apply(s - 1, e, x);
        } else {
            int s, e;
            std::cin >> s >> e;
            std::cout << seg.prod(s - 1, e).sum << '\n';
        }
    }
}