题目链接

题解：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#define ll long long
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e15;
const int mod=1e9+7;
const double eps=1e-8;
const int maxn=500100;

struct node
{
    int l,r;
    int maxx,maxl,se,cnt;
    int addmaxx,addmaxl,addse,addsel;
    ll sum;
}t[maxn<<2];

int a[maxn];

void pushup(int cnt)
{
    t[cnt].maxx=max(t[lc].maxx,t[rc].maxx);
    t[cnt].maxl=max(t[lc].maxl,t[rc].maxl);
    t[cnt].sum=t[lc].sum+t[rc].sum;

    if(t[lc].maxx==t[rc].maxx)
    {
        t[cnt].cnt=t[lc].cnt+t[rc].cnt;
        t[cnt].se=max(t[lc].se,t[rc].se);
    }
    else if(t[lc].maxx>t[rc].maxx)
    {
        t[cnt].cnt=t[lc].cnt;
        t[cnt].se=max(t[lc].se,t[rc].maxx);
    }
    else
    {
        t[cnt].cnt=t[rc].cnt;
        t[cnt].se=max(t[lc].maxx,t[rc].se);
    }
}

void update(int cnt,int addmaxx,int addmaxl,int addse,int addsel)
{
    t[cnt].sum+=1ll*addmaxx*t[cnt].cnt+1ll*addse*(t[cnt].r-t[cnt].l+1-t[cnt].cnt);
    t[cnt].maxl=max(t[cnt].maxl,t[cnt].maxx+addmaxl);
    t[cnt].addmaxl=max(t[cnt].addmaxl,t[cnt].addmaxx+addmaxl);
    t[cnt].maxx+=addmaxx;
    t[cnt].addmaxx+=addmaxx;
    t[cnt].addsel=max(t[cnt].addsel,t[cnt].addse+addsel);
    if(t[cnt].se!=-inf) t[cnt].se+=addse;
    t[cnt].addse+=addse;
}

void pushdown(int cnt)
{
    int nowmaxx=max(t[lc].maxx,t[rc].maxx);

    if(t[lc].maxx==nowmaxx) update(lc,t[cnt].addmaxx,t[cnt].addmaxl,t[cnt].addse,t[cnt].addsel);
    else update(lc,t[cnt].addse,t[cnt].addsel,t[cnt].addse,t[cnt].addsel);

    if(t[rc].maxx==nowmaxx) update(rc,t[cnt].addmaxx,t[cnt].addmaxl,t[cnt].addse,t[cnt].addsel);
    else update(rc,t[cnt].addse,t[cnt].addsel,t[cnt].addse,t[cnt].addsel);

    t[cnt].addmaxx=t[cnt].addmaxl=t[cnt].addse=t[cnt].addsel=0;
}

void build(int l,int r,int cnt)
{
    t[cnt].l=l,t[cnt].r=r;
    t[cnt].sum=t[cnt].maxx=t[cnt].maxl=t[cnt].se=t[cnt].cnt=0;
    t[cnt].addmaxx=t[cnt].addmaxl=t[cnt].addse=t[cnt].addsel=0;
    if(l==r)
    {
        t[cnt].sum=t[cnt].maxx=t[cnt].maxl=a[l];
        t[cnt].se=-inf,t[cnt].cnt=1;
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,lc);
    build(mid+1,r,rc);
    pushup(cnt);
}

void change1(int l,int r,int cnt,int k)
{
    if(l<=t[cnt].l&&t[cnt].r<=r)
    {
        update(cnt,k,k,k,k);
        return ;
    }
    pushdown(cnt);
    if(l<=t[lc].r) change1(l,r,lc,k);
    if(r>=t[rc].l) change1(l,r,rc,k);
    pushup(cnt);
}

void change2(int l,int r,int cnt,int v)
{
    if(v>=t[cnt].maxx) return ;
    if(l<=t[cnt].l&&t[cnt].r<=r&&v>t[cnt].se)
    {
        update(cnt,v-t[cnt].maxx,v-t[cnt].maxx,0,0);
        return ;
    }
    pushdown(cnt);
    if(l<=t[lc].r) change2(l,r,lc,v);
    if(r>=t[rc].l) change2(l,r,rc,v);
    pushup(cnt);
}

ll ask3(int l,int r,int cnt)
{
    if(l<=t[cnt].l&&t[cnt].r<=r)
        return t[cnt].sum;
    pushdown(cnt);
    ll ans=0;
    if(l<=t[lc].r) ans+=ask3(l,r,lc);
    if(r>=t[rc].l) ans+=ask3(l,r,rc);
    return ans;
}

int ask4(int l,int r,int cnt)
{
    if(l<=t[cnt].l&&t[cnt].r<=r)
        return t[cnt].maxx;
    pushdown(cnt);
    int maxx=-inf;
    if(l<=t[lc].r) maxx=max(maxx,ask4(l,r,lc));
    if(r>=t[rc].l) maxx=max(maxx,ask4(l,r,rc));
    return maxx;
}

int ask5(int l,int r,int cnt)
{
    if(l<=t[cnt].l&&t[cnt].r<=r)
        return t[cnt].maxl;
    pushdown(cnt);
    int maxx=-inf;
    if(l<=t[lc].r) maxx=max(maxx,ask5(l,r,lc));
    if(r>=t[rc].l) maxx=max(maxx,ask5(l,r,rc));
    return maxx;
}

int main(void)
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    build(1,n,1);

    int op,l,r,k,v;
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%d",&l,&r,&k);
            change1(l,r,1,k);
        }
        else if(op==2)
        {
            scanf("%d%d%d",&l,&r,&v);
            change2(l,r,1,v);
        }
        else if(op==3)
        {
            scanf("%d%d",&l,&r);
            printf("%lld\n",ask3(l,r,1));
        }
        else if(op==4)
        {
            scanf("%d%d",&l,&r);
            printf("%d\n",ask4(l,r,1));
        }
        else if(op==5)
        {
            scanf("%d%d",&l,&r);
            printf("%d\n",ask5(l,r,1));
        }
    }
    return 0;
}