洛谷P3372_template

参考：将线段树封装成模板

线段树封装成模板需要C++20 :)

#include<bits/stdc++.h>
using namespace std;

using ll=long long;

template < typename T, auto op, T e, typename F, auto mapping, auto composition,
           F e1 >
class segtree
{
    int n;
    vector< T > v;
    vector< F > lazy;
    void build(int now, int l, int r, T a[])
    {
        if(l == r)
        {
            v[now] = a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(now * 2, l, mid, a);
        build(now * 2 + 1, mid + 1, r, a);
        v[now] = op(v[now * 2], v[now * 2 + 1]);
    }
    void pushup(int k) { v[k] = op(v[k * 2], v[k * 2 + 1]); }
    void pushdown(int k, int l, int r)
    {
        v[k] = mapping(v[k], lazy[k], l, r);
        if (l != r) {
            lazy[k * 2] = composition(lazy[k * 2], lazy[k]);
            lazy[k * 2 + 1] = composition(lazy[k * 2 + 1], lazy[k]);
        }
        lazy[k] = e1;
    }

    void modify(int now, int ql, int qr, int l, int r, F x)
    {
        pushdown(now, l, r);
        if (l > qr || r < ql) return;
        if (l >= ql && r <= qr) {
            lazy[now] = x;
            pushdown(now, l, r);
            return;
        }
        modify(now * 2, ql, qr, l, (l + r) / 2, x);
        modify(now * 2 + 1, ql, qr, (l + r) / 2 + 1, r, x);
        pushup(now);
    }
    T query(int now, int ql, int qr, int l, int r)
    {
        pushdown(now, l, r);
        if (l > qr || r < ql) return e;
        if (l >= ql && r <= qr) return v[now];
        return op(query(now * 2, ql, qr, l, (l + r) / 2),
                  query(now * 2 + 1, ql, qr, (l + r) / 2 + 1, r));
    }

public:
    segtree(T a[], int n) : segtree(n)
    {
        build(1, 1, n, a);
    }
    segtree(int n)
    {
        this->n = n;
        v = vector< T >(n << 2, e);
        lazy = vector< F >(n << 2, e1);
    }

    void modify(int l, int r, F x) { modify(1, l, r, 1, n, x); }
    T query(int l, int r) { return query(1, l, r, 1, n); }
};

template<typename T>
T MAX(T x, T y) {if(x > y) return x; else return y;}
template<typename T>
T MIN(T x, T y) {if(x < y) return x; else return y;}
template<typename T>
T PLUS(T x, T y) {return x + y;}

/*  Note:
    typename T, auto op, T e, 
    typename F, auto mapping, auto composition,
    F e1
*/
using segtree_add=segtree< ll, PLUS<ll>, 0, ll,[](ll x, ll lazy, int l, int r) { return x + (r - l + 1) * lazy; }, PLUS<ll>, 0 >;
using segtree_min=segtree< ll, MIN<ll>, (ll)1e9, ll,[](ll x, ll lazy, int l, int r) { return x+lazy; },PLUS<ll>, 0 >;

ll n,m,a[(int)1e5+9];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>a[i];
    segtree_add seg(a,n);
    for(int i=1,op,x,y,z;i<=m;++i){
        cin>>op>>x>>y;
        if(op&1){
            cin>>z;
            seg.modify(x,y,z);
        }else cout<<seg.query(x,y)<<"\n";
    }
}