:heavy_check_mark: test/AOJ/DSL_2_G.test.cpp

Depends on

Code

#define PROBLEM                                                                \
    "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G"
#include <bits/stdc++.h>

#include "library/algebra/lazy/AddSum.hpp"
#include "library/segtree/LazySegmentTree.hpp"

using ll = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    std::cin >> n >> q;
    LazySegmentTree<LazyAddSum<ll>> seg(cnt_init(n, 0LL));

    while (q--) {
        int t, l, r;
        std::cin >> t >> l >> r;
        l--;
        if (t)
            std::cout << seg.prod(l, r).first << "\n";
        else {
            int x;
            std::cin >> x;
            seg.apply(l, r, x);
        }
    }
}
#line 1 "test/AOJ/DSL_2_G.test.cpp"
#define PROBLEM                                                                \
    "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G"
#include <bits/stdc++.h>

#line 2 "library/algebra/group/Add.hpp"
template<typename X>
struct GroupAdd {
  using value_type = X;
  static constexpr X op(const X &x, const X &y) noexcept { return x + y; }
  static constexpr void Rchop(X&x, const X&y){ x+=y; }
  static constexpr void Lchop(const X&x, X&y){ y+=x; }
  static constexpr X inverse(const X &x) noexcept { return -x; }
  static constexpr X power(const X &x, long long n) noexcept { return X(n) * x; }
  static constexpr X unit() { return X(0); }
  static constexpr bool commute = true;
};
#line 1 "library/algebra/group/CntSum.hpp"
template <typename X> struct GroupCntSum {
    using P = std::pair<X, X>;
    using value_type = P;
    static constexpr P op(const P &x, const P &y) {
        return {x.first + y.first, x.second + y.second};
    }
    static constexpr void Rchop(P &x, const P &y) {
        x.first += y.first;
        x.second += y.second;
    }
    static constexpr void Lchop(const P &x, P &y) {
        y.first += x.first;
        y.second += x.second;
    }
    static constexpr P inverse(const P &x) { return {-x.fi, -x.se}; }
    static constexpr P unit() { return {0, 0}; }
    static constexpr bool commute = true;
};
template <typename X> std::vector<std::pair<X, X>> cnt_init(int n, const X &x) {
    return std::vector<std::pair<X, X>>(n, {x, 1});
}
template <typename X>
std::vector<std::pair<X, X>> cnt_init(const std::vector<X> &v) {
    int n = v.size();
    std::vector<std::pair<X, X>> res(n);
    for (int i = 0; i < n; i++)
        res[i] = {v[i], 1};
    return res;
}
#line 4 "library/algebra/lazy/AddSum.hpp"
template <typename X> struct LazyAddSum {
    using MX = GroupCntSum<X>;
    using MF = GroupAdd<X>;
    using S = typename MX::value_type;
    static constexpr S mapping(const X &f, const S &x) {
        return {x.first + f * x.second, x.second};
    }
};
#line 2 "library/segtree/LazySegmentTree.hpp"

template <typename Lazy> class LazySegmentTree {
    using MX = typename Lazy::MX;
    using MF = typename Lazy::MF;
    using X = typename MX::value_type;
    using F = typename MF::value_type;
    int n, log, size;
    std::vector<X> dat;
    std::vector<F> laz;

    X reflect(int k) {
        if (k < size)
            return Lazy::mapping(laz[k], dat[k]);
        return dat[k];
    }
    void point_apply(int k, const F &f) {
        if (k < size)
            MF::Lchop(f, laz[k]);
        else
            dat[k] = Lazy::mapping(f, dat[k]);
    }
    void push(int k) {
        dat[k] = reflect(k);
        point_apply(2 * k, laz[k]);
        point_apply(2 * k + 1, laz[k]);
        laz[k] = MF::unit();
    }
    void thrust(int k) {
        for (int i = log; i; i--)
            push(k >> i);
    }
    void update(int i) { dat[i] = MX::op(reflect(2 * i), reflect(2 * i + 1)); }
    void recalc(int k) {
        while (k >>= 1)
            update(k);
    }

  public:
    LazySegmentTree() : LazySegmentTree(0) {}
    LazySegmentTree(int n) : LazySegmentTree(std::vector<X>(n, MX::unit())) {}
    LazySegmentTree(const std::vector<X> &v) : n(v.size()) {
        for (log = 1; (1 << log) < n; log++) {
        }
        size = 1 << log;
        dat.assign(size << 1, MX::unit());
        laz.assign(size, MF::unit());
        for (int i = 0; i < n; ++i)
            dat[size + i] = v[i];
        for (int i = size - 1; i >= 1; --i)
            update(i);
    }

    void set(int p, X x) {
        assert(0 <= p and p < n);
        thrust(p += size);
        dat[p] = x;
        recalc(p);
    }

    X operator[](int p) {
        assert(0 <= p and p < n);
        thrust(p += size);
        return reflect(p);
    }

    X prod(int L, int R) {
        assert(0 <= L and L <= R and R <= n);
        if (L == R)
            return MX::unit();
        thrust(L += size);
        thrust((R += size - 1)++);
        X vl = MX::unit(), vr = MX::unit();
        while (L < R) {
            if (L & 1)
                MX::Rchop(vl, reflect(L++));
            if (R & 1)
                MX::Lchop(reflect(--R), vr);
            L >>= 1, R >>= 1;
        }
        return MX::op(vl, vr);
    }

    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= n);
        if (l == r)
            return;
        thrust(l += size);
        thrust(r += size - 1);
        for (int L = l, R = r + 1; L < R; L >>= 1, R >>= 1) {
            if (L & 1)
                point_apply(L++, f);
            if (R & 1)
                point_apply(--R, f);
        }
        recalc(l);
        recalc(r);
    }
};
#line 7 "test/AOJ/DSL_2_G.test.cpp"

using ll = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    std::cin >> n >> q;
    LazySegmentTree<LazyAddSum<ll>> seg(cnt_init(n, 0LL));

    while (q--) {
        int t, l, r;
        std::cin >> t >> l >> r;
        l--;
        if (t)
            std::cout << seg.prod(l, r).first << "\n";
        else {
            int x;
            std::cin >> x;
            seg.apply(l, r, x);
        }
    }
}
Back to top page