洛谷P1253_扶苏的问题

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

using ll=long long;
const ll inf = 1e18;

template < typename T, auto op, auto e, typename F, auto mapping, auto composition,
           auto 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
*/
struct F {ll add, cover;};
using segtree_max_edit=segtree< ll, [](ll x, ll y) { return max(x, y); }, [](){return -inf;}, F,
         [](ll x, F t, int l, int r) {
             if (t.cover != inf)
                 return t.cover;
             else
                 return x + t.add;
         },
         [](F t1, F t2) -> F {
             if (t2.cover != inf) return{ 0, t2.cover };
             else 
             {
                 if (t1.cover != inf) return { 0, t1.cover + t2.add };
                 else return { t1.add + t2.add, inf };
             }
         }, 
         []()->F {return { 0, inf };} >;

ll n,q,a[(int)1e6+9];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;++i)cin>>a[i];
    segtree_max_edit seg(a,n);
    for(int i=1,op,l,r,x;i<=q;++i){
        cin>>op>>l>>r;
        if(op==1){
            cin>>x;
            seg.modify(l,r,F{0,x});
        }else if(op==2){
            cin>>x;
            seg.modify(l,r,F{x,inf});
        }else cout<<seg.query(l,r)<<"\n";
    }
}