吉司机线段树

这里不会挂涩图了，相册或者公告板自取

调了一晚上，刚改出来，有时间再更。

P6242 【模板】线段树 3

Code

#include<cstdio>
#include<algorithm>

#define LL long long

using namespace std;

const LL INF = 1e18;
const int MAXN = 5e5 + 10;
int n, m;
LL num[MAXN];

inline LL read(){
    LL x = 0, f = 1;
    char c = getchar();

    while(c < '0' || c > '9'){
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }

    return x * f;
}

struct Segment_Tree{
    struct Tree{
        int l, r;
        LL sum;
        LL max_st, max_nd, max_his; //分别是：区间最大值，严格区间次大值，区间最大值的个数
        LL num_max;
        LL lazy_st, lazy_sth, lazy_nd, lazy_ndh;
        //分别是：最大值加减标记，最大值历史最大的加减标记
        //       非最大值加减标记，非最大值历史最大的加减标记
    }tr[MAXN << 2];

    inline int lson(int rt){
        return rt << 1;
    }

    inline int rson(int rt){
        return rt << 1 | 1;
    }

    inline void Pushup(int rt){
        tr[rt].sum = tr[lson(rt)].sum + tr[rson(rt)].sum;
        tr[rt].max_st = max(tr[lson(rt)].max_st, tr[rson(rt)].max_st);
        tr[rt].max_his = max(tr[lson(rt)].max_his, tr[rson(rt)].max_his);

        if(tr[lson(rt)].max_st == tr[rson(rt)].max_st){
            tr[rt].num_max = tr[lson(rt)].num_max + tr[rson(rt)].num_max;
            tr[rt].max_nd = max(tr[lson(rt)].max_nd, tr[rson(rt)].max_nd);
        }
        else if(tr[lson(rt)].max_st > tr[rson(rt)].max_st){
            tr[rt].num_max = tr[lson(rt)].num_max;
            tr[rt].max_nd = max(tr[lson(rt)].max_nd, tr[rson(rt)].max_st);
        }
        else if(tr[lson(rt)].max_st < tr[rson(rt)].max_st){
            tr[rt].num_max = tr[rson(rt)].num_max;
            tr[rt].max_nd = max(tr[lson(rt)].max_st, tr[rson(rt)].max_nd);
        }
    }

    void Build(int rt, int l, int r){
        tr[rt].l = l;
        tr[rt].r = r;

        if(l == r){
            tr[rt].sum = tr[rt].max_st = tr[rt].max_his = num[l];
            tr[rt].num_max = 1;
            tr[rt].max_nd = -INF;

            return;
        }

        int mid = (l + r) >> 1;
        Build(lson(rt), l, mid);
        Build(rson(rt), mid + 1, r);

        Pushup(rt);
    }

    inline void Modify(int rt, LL val_st, LL val_sth, LL val_nd, LL val_ndh){
        tr[rt].sum += (tr[rt].num_max * val_st + (tr[rt].r - tr[rt].l + 1 - tr[rt].num_max) * val_nd);
        tr[rt].max_his = max(tr[rt].max_his, tr[rt].max_st + val_sth);
        tr[rt].max_st += val_st;

        if(tr[rt].max_nd != -INF) tr[rt].max_nd += val_nd;

        tr[rt].lazy_sth = max(tr[rt].lazy_sth, tr[rt].lazy_st + val_sth);
        tr[rt].lazy_st += val_st;
        tr[rt].lazy_ndh = max(tr[rt].lazy_ndh, tr[rt].lazy_nd + val_ndh);
        tr[rt].lazy_nd += val_nd;
    }

    inline void Pushdown(int rt){
        int maxn = max(tr[lson(rt)].max_st, tr[rson(rt)].max_st);

        if(tr[lson(rt)].max_st == maxn)
            Modify(lson(rt), tr[rt].lazy_st, tr[rt].lazy_sth, tr[rt].lazy_nd, tr[rt].lazy_ndh);
        else Modify(lson(rt), tr[rt].lazy_nd, tr[rt].lazy_ndh, tr[rt].lazy_nd, tr[rt].lazy_ndh);

        if(tr[rson(rt)].max_st == maxn)
            Modify(rson(rt), tr[rt].lazy_st, tr[rt].lazy_sth, tr[rt].lazy_nd, tr[rt].lazy_ndh);
        else Modify(rson(rt), tr[rt].lazy_nd, tr[rt].lazy_ndh, tr[rt].lazy_nd, tr[rt].lazy_ndh);

        tr[rt].lazy_st = 0, tr[rt].lazy_sth = 0, tr[rt].lazy_nd = 0, tr[rt].lazy_ndh = 0;
    }

    void Update_Add(int rt, int l, int r, LL val){
        if(tr[rt].l >= l && tr[rt].r <= r){
            Modify(rt, val, val, val, val);
            return;
        }

        Pushdown(rt);

        int mid = (tr[rt].l + tr[rt].r) >> 1;
        if(l <= mid) Update_Add(lson(rt), l, r, val);
        if(r > mid) Update_Add(rson(rt), l, r, val);

        Pushup(rt);
    }

    void Update_Min(int rt, int l, int r, LL val){
        if(tr[rt].max_st <= val) return;

        if(tr[rt].l >= l && tr[rt].r <= r && tr[rt].max_nd < val){
            Modify(rt, val - tr[rt].max_st, val - tr[rt].max_st, 0, 0);
            return;
        }

        Pushdown(rt);

        int mid = (tr[rt].l + tr[rt].r) >> 1;
        if(l <= mid) Update_Min(lson(rt), l, r, val);
        if(r > mid) Update_Min(rson(rt), l, r, val);

        Pushup(rt);
    }

    LL Query_Sum(int rt, int l, int r){
        if(tr[rt].l >= l && tr[rt].r <= r)
            return tr[rt].sum;
        
        Pushdown(rt);

        LL ans = 0;
        int mid = (tr[rt].l + tr[rt].r) >> 1;
        if(l <= mid) ans += Query_Sum(lson(rt), l, r);
        if(r > mid) ans += Query_Sum(rson(rt), l, r);

        return ans;
    }

    LL Query_Max(int rt, int l, int r){
        if(tr[rt].l >= l && tr[rt].r <= r)
            return tr[rt].max_st;
        
        Pushdown(rt);

        LL ans = -INF;
        int mid = (tr[rt].l + tr[rt].r) >> 1;
        if(l <= mid) ans = max(ans, Query_Max(lson(rt), l, r));
        if(r > mid) ans = max(ans, Query_Max(rson(rt), l, r));

        return ans;
    }

    LL Query_His(int rt, int l, int r){
        if(tr[rt].l >= l && tr[rt].r <= r)
            return tr[rt].max_his;

        Pushdown(rt);

        LL ans = -INF;
        int mid = (tr[rt].l + tr[rt].r) >> 1;
        if(l <= mid) ans = max(ans, Query_His(lson(rt), l, r));
        if(r > mid) ans = max(ans, Query_His(rson(rt), l, r));

        return ans;
    }
}S;

int main(){
    n = read(), m = read();
    for(register int i = 1; i <= n; i++)
        num[i] = read();
    
    S.Build(1, 1, n);

    for(register int i = 1; i <= m; i++){
        int opt;
        opt = read();

        if(opt == 1){
            int l, r, k;
            l = read(), r = read(), k = read();
            S.Update_Add(1, l, r, k);
        }
        else if(opt == 2){
            int l, r, v;
            l = read(), r = read(), v = read();
            S.Update_Min(1, l, r, v);
        }
        else if(opt == 3){
            int l, r;
            l = read(), r = read();
            printf("%lld\n", S.Query_Sum(1, l, r));
        }
        else if(opt == 4){
            int l, r;
            l = read(), r = read();
            printf("%lld\n", S.Query_Max(1, l, r));
        }
        else{
            int l, r;
            l = read(), r = read();
            printf("%lld\n", S.Query_His(1, l, r));
        }
    }

    return 0;
}