[10999] 구간 합 구하기 2

https://www.acmicpc.net/problem/10999

10999번: 구간 합 구하기 2

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

template <typename NodeType, typename LazyType, typename F_Merge,

          typename F_Update,

          typename F_Composition>

struct LazySegTree {  // 1-indexed

   public:

    using A = NodeType;

    using B = LazyType;

    LazySegTree() : LazySegTree(0, A(), B()) {}

    explicit LazySegTree(int n, const A& e, const B& id)

        : n(n),

          e(e),

          id(id),

          lg(Log2(n)),

          sz(1 << lg),

          tree(sz << 1, e),

          lazy(sz, id) {}

    void Set(int i, const A& val) { tree[--i | sz] = val; }

    void Init() {

        for (int i = sz - 1; i; i--) Pull(i);

    }

    void Update(int i, const B& f) {

        --i |= sz;

        for (int j = lg; j; j--) Push(i >> j);

        Apply(i, f);

        for (int j = 1; j <= lg; j++) Pull(i >> j);

    }

    void Update(int l, int r, const B& f) {

        --l |= sz, --r |= sz;

        for (int i = lg; i; i--) {

            if (l >> i << i != l) Push(l >> i);

            if (r + 1 >> i << i != r + 1) Push(r >> i);

        }

        for (int L = l, R = r; L <= R; L >>= 1, R >>= 1) {

            if (L & 1) Apply(L++, f);

            if (~R & 1) Apply(R--, f);

        }

        for (int i = 1; i <= lg; i++) {

            if (l >> i << i != l) Pull(l >> i);

            if (r + 1 >> i << i != r + 1) Pull(r >> i);

        }

    }

    A Query(int i) {

        --i |= sz;

        for (int j = lg; j; j--) Push(i >> j);

        return tree[i];

    }

    A Query(int l, int r) {

        A L = e, R = e;

        --l |= sz, --r |= sz;

        for (int i = lg; i; i--) {

            if (l >> i << i != l) Push(l >> i);

            if (r + 1 >> i << i != r + 1) Push(r >> i);

        }

        for (; l <= r; l >>= 1, r >>= 1) {

            if (l & 1) L = M(L, tree[l++]);

            if (~r & 1) R = M(tree[r--], R);

        }

        return M(L, R);

    }

   private:

    const int n, lg, sz;

    const A e;

    const B id;

    vector<A> tree;

    vector<B> lazy;

    F_Merge M;

    F_Update U;

    F_Composition C;

    static int Log2(int n) {

        int ret = 0;

        while (n > 1 << ret) ret++;

        return ret;

    }

    void Apply(int i, const B& f) {

        tree[i] = U(f, tree[i]);

        if (i < sz) lazy[i] = C(f, lazy[i]);

    }

    void Push(int i) {

        Apply(i << 1, lazy[i]);

        Apply(i << 1 | 1, lazy[i]);

        lazy[i] = id;

    }

    void Pull(int i) { tree[i] = M(tree[i << 1], tree[i << 1 | 1]); }

};

//------------------------------------------

struct NodeType {

    ll val, sz;

    constexpr NodeType(ll _val, ll _sz) : val(_val), sz(_sz) {}

};

using LazyType = ll;

// struct LazyType {};

constexpr NodeType e = NodeType(0, 0);

constexpr LazyType id = 0;

struct F_Merge {

    NodeType operator()(const NodeType& A, const NodeType& B) const {

        return NodeType(A.val + B.val, A.sz + B.sz);

    }

};

struct F_Update {

    NodeType operator()(const LazyType& A, const NodeType& B) const {

        return NodeType(B.val + A * B.sz, B.sz);

    }

};

struct F_Composition {

    LazyType operator()(const LazyType& A, const LazyType& B) const {

        return A + B;

    }

};

//------------------------------------------

ll n, m, k;

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n >> m >> k;

    LazySegTree<NodeType, LazyType, F_Merge, F_Update, F_Composition> segTree(

        n, e, id);

    ll i, S = m + k;

    for (i = 0; i < n; i++) {

        ll x;

        cin >> x;

        segTree.Set(i + 1, NodeType(x, 1));

    }

    segTree.Init();

    for (i = 0; i < S; i++) {

        ll op;

        cin >> op;

        if (op == 1) {

            ll A, B, C;

            cin >> A >> B >> C;

            segTree.Update(A, B, C);

        } else if (op == 2) {

            ll A, B;

            cin >> A >> B;

            cout << segTree.Query(A, B).val << '\n';

        }

    }

    return 0;

}

---

https://www.acmicpc.net/blog/view/117