题目 P6242

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int N = 5e5 + 10;
struct node{
    int hmax,nmax,se,cnt,ad,admax;
    int mad,madmax;
    ll sum;
}tr[4 * N];
int n,m,v,l,r,opt;
void print(){
    for(int i = 1;i <= 10 ; ++i){
        printf("%d %lld %d %d %d %d %d %d %d %d\n",i,tr[i].sum,tr[i].nmax,tr[i].hmax,tr[i].se,tr[i].cnt,tr[i].ad,tr[i].admax,tr[i].mad,tr[i].madmax);
    }
}
void update(int x){
    tr[x].hmax = max(tr[x << 1].hmax,tr[x << 1 | 1].hmax);
    tr[x].nmax = max(tr[x << 1].nmax,tr[x << 1 | 1].nmax);
    tr[x].sum = tr[x << 1].sum + tr[x << 1 | 1].sum;
    if(tr[x << 1].nmax == tr[x << 1 | 1].nmax){
        tr[x].se = max(tr[x << 1].se,tr[x << 1 | 1].se);
        tr[x].cnt = tr[x << 1].cnt + tr[x << 1 | 1].cnt;
    }else if(tr[x << 1].nmax > tr[x << 1 | 1].nmax){
        tr[x].se = max(tr[x << 1 | 1].nmax,tr[x << 1].se);
        tr[x].cnt = tr[x << 1].cnt;
    }else{
        tr[x].se = max(tr[x << 1].nmax,tr[x << 1 | 1].se);
        tr[x].cnt = tr[x << 1 | 1].cnt;
    }
}
void addtag(int x,int ad,int admax,int mad,int madmax,int len){
    tr[x].sum += 1ll * (len - tr[x].cnt) * ad + 1ll * tr[x].cnt * mad;
    tr[x].hmax = max(tr[x].hmax,tr[x].nmax + madmax);
    tr[x].admax = max(tr[x].admax,tr[x].ad + admax);
    tr[x].madmax = max(tr[x].madmax,tr[x].mad + madmax);
    tr[x].nmax += mad;tr[x].se += ad;
    tr[x].mad += mad;tr[x].ad += ad;
}
void downtag(int x,int len1,int len2){
    addtag(x << 1,tr[x].ad,tr[x].admax,tr[x].mad,tr[x].madmax,len1);
    addtag(x << 1 | 1,tr[x].ad,tr[x].admax,tr[x].mad,tr[x].madmax,len2);
    tr[x].madmax = tr[x].mad = tr[x].ad = tr[x].admax = 0;
}
void build(int x,int l,int r,int v,int pos){
    if(l == r){
        tr[x].hmax = tr[x].nmax = tr[x].sum = v;
        tr[x].se = -1e9;
        tr[x].cnt = 1;
        return ;
    }
    int mid = l + r >> 1;
    if(pos <= mid)build(x << 1,l,mid,v,pos);
    else if(pos > mid)build(x << 1 | 1,mid + 1,r,v,pos);
    update(x);
}
void add(int x,int l,int r,int L,int R,int v){
    if(L <= l && r <= R){
        addtag(x,v,v,v,v,r - l + 1);
        return ;
    }
    int mid = l + r >> 1;
    downtag(x,mid - l + 1,r - mid);
    if(L <= mid)add(x << 1,l,mid,L,R,v);
    if(R > mid)add(x << 1 | 1,mid + 1,r,L,R,v);
    update(x);
}
void amin(int x,int l,int r,int L,int R,int v){
    // cout<<'f'<<x<<' '<<tr[x].nmax<<' '<<v<<endl;
    if(v >= tr[x].nmax || l > R || r < L){
        // cout<<"out";
        // cout<<"pd:"<<L<<' '<<l<<' '<<r<<' '<<R<<endl;    
        return ;

    }
    if(L <= l && r <= R && tr[x].se < v){
        // cout<<'a';
        addtag(x,0,0,v - tr[x].nmax,v - tr[x].nmax,r - l + 1);
        return ;
    };
    int mid = l + r >> 1;
    downtag(x,mid - l + 1,r - mid);
    amin(x << 1,l,mid,L,R,v);
    amin(x << 1 | 1,mid + 1,r,L,R,v);
    update(x);
}
ll qsum(int x,int l,int r,int L,int R){
    if(L <= l && r <= R){
        return tr[x].sum;
    }
    int mid = l + r >> 1;
    ll ans = 0;
    downtag(x,mid - l + 1,r - mid);
    if(L <= mid)ans += qsum(x << 1,l,mid,L,R);
    if(R > mid)ans += qsum(x << 1 | 1,mid + 1,r,L,R);
    return ans;
}
ll qnmax(int x,int l,int r,int L,int R){
    if(L <= l && r <= R){
        return tr[x].nmax;
    }
    int mid = l + r >> 1;
    ll ans = -1e9;
    downtag(x,mid - l + 1,r - mid);
    if(L <= mid)ans = max(ans,qnmax(x << 1,l,mid,L,R));
    if(R > mid)ans = max(ans,qnmax(x << 1 | 1,mid + 1,r,L,R));
    return ans;
}
ll qhmax(int x,int l,int r,int L,int R){
    if(L <= l && r <= R){
        return tr[x].hmax;
    }
    int mid = l + r >> 1;
    ll ans = -1e9;
    downtag(x,mid - l + 1,r - mid);
    if(L <= mid)ans = max(ans,qhmax(x << 1,l,mid,L,R));
    if(R > mid)ans = max(ans,qhmax(x << 1 | 1,mid + 1,r,L,R));
    return ans;
}
void input(){
    cin>>n>>m;
    for(int i = 1;i <= n; ++i){
        cin>>v;
        build(1,1,n,v,i);
    }
}
void op(){
    for(int i = 1;i <= m; ++i){
        cin>>opt>>l>>r;
        if(opt == 1){
            cin>>v;
            add(1,1,n,l,r,v);
        }else if(opt == 2){
            cin>>v;
            amin(1,1,n,l,r,v);
        }else if(opt == 3){
            cout<<qsum(1,1,n,l,r)<<'\n';
        }else if(opt == 4){
            cout<<qnmax(1,1,n,l,r)<<'\n';
        }else if(opt == 5){
            cout<<qhmax(1,1,n,l,r)<<'\n';
        }
        // print();
    }
}
int main(){
    // cin.tie(0)->sync_with_stdio(false);
    input();
    op();
    return 0;
}