#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
ll n,m,a[500005],v,l,r;
struct node
{
    ll l,r,s,del_a,del_b,del_a1,del_b1,maxa,maxb,se,cnt;
}tr[2000100];
ll read()
{
	char ch=getchar();
	ll x=0,f=1;
	while(ch<'0'||ch>'9')
	{
	    if(ch=='-') f=-1;
	    ch=getchar();
	}
	while('0'<=ch && ch<='9')
	{
	    x=x*10+ch-'0';
	    ch=getchar();
	}
	return x*f;
}
void pushup(ll u)
{
 	tr[u].s=tr[u<<1].s+tr[u<<1|1].s;
 	tr[u].maxa=max(tr[u<<1].maxa,tr[u<<1|1].maxa);
 	tr[u].maxb=max(tr[u<<1].maxb,tr[u<<1|1].maxb);
 	if(tr[u<<1].maxa==tr[u<<1|1].maxa)
	{
		tr[u].se=max(tr[u<<1].se,tr[u<<1|1].se);
		tr[u].cnt=tr[u<<1].cnt+tr[u<<1|1].cnt;
	}
	else if(tr[u<<1].maxa>tr[u<<1|1].maxa)
	{
		tr[u].se=max(tr[u<<1].se,tr[u<<1|1].maxa);
		tr[u].cnt=tr[u<<1].cnt;
	}
	else
	{
		tr[u].se=max(tr[u<<1].maxa,tr[u<<1|1].se);
		tr[u].cnt=tr[u<<1|1].cnt;
	}
}
void pushup2(ll u,ll k1,ll k2,ll k3,ll k4)
{
	tr[u].s+=k1*tr[u].cnt+k3*(tr[u].r-tr[u].l+1-tr[u].cnt);
	tr[u].maxb=max(tr[u].maxb,tr[u].maxa+k2);
	tr[u].del_b=max(tr[u].del_b,tr[u].del_a+k2);
	tr[u].del_b1=max(tr[u].del_b1,tr[u].del_a1+k4);
	tr[u].maxa+=k1;
	tr[u].del_a+=k1;
	tr[u].del_a1+=k3;
	if(tr[u].se!=-1e18) tr[u].se+=k3;
}
void pushdown(ll u)
{
	ll maxn=max(tr[u<<1].maxa,tr[u<<1|1].maxa);
	if(tr[u<<1].maxa==maxn)
	{
		pushup2(u<<1,tr[u].del_a,tr[u].del_b,tr[u].del_a1,tr[u].del_b1);
	}
	else pushup2(u<<1,tr[u].del_a1,tr[u].del_b1,tr[u].del_a1,tr[u].del_b1);
	if(tr[u<<1|1].maxa==maxn)
	{
		pushup2(u<<1|1,tr[u].del_a,tr[u].del_b,tr[u].del_a1,tr[u].del_b1);
	}
	else pushup2(u<<1|1,tr[u].del_a1,tr[u].del_b1,tr[u].del_a1,tr[u].del_b1);
	tr[u].del_a=tr[u].del_b=tr[u].del_a1=tr[u].del_b1=0;
}
void build(ll u,ll l,ll r)
{
	tr[u].l=l;
	tr[u].r=r;
	if(l==r)
	{
		tr[u].s=a[l];
		tr[u].maxa=a[l];
		tr[u].maxb=a[l];
		tr[u].se=-1e18;
		tr[u].cnt=1;
		return;
	}
	ll mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	pushup(u);
}
void modify_add(ll u)
{
	if(tr[u].l>r || tr[u].r<l) return;
	if(l<=tr[u].l && tr[u].r<=r)
	{
	    pushup2(u,v,0,v,0);
		return;
	}
	pushdown(u);
	modify_add(u<<1);
	modify_add(u<<1|1);
	pushup(u);
}
void modify_min(ll u)
{
	if(tr[u].l>r || tr[u].r<l || v>=tr[u].maxa) return;
	if(l<=tr[u].l && tr[u].r<=r && v>tr[u].se)
	{
	    pushup2(u,v-tr[u].maxa,v-tr[u].maxa,0,0);
		return;
	}
	pushdown(u);
	modify_min(u<<1);
	modify_min(u<<1|1);
	pushup(u);
}
ll querymaxa(ll u)
{
	if(tr[u].l>r || tr[u].r<l) return -1e18;
	if(l<=tr[u].l && tr[u].r<=r) return tr[u].maxa;
	pushdown(u);
	return max(querymaxa(u<<1),querymaxa(u<<1|1));
}
ll querymaxb(ll u)
{
	if(tr[u].l>r || tr[u].r<l) return -1e18;
	if(l<=tr[u].l && tr[u].r<=r) return tr[u].maxb;
	pushdown(u);
	return max(querymaxb(u<<1),querymaxb(u<<1|1));
}
ll getsum(ll u)
{
	if(tr[u].l>r || tr[u].r<l) return 0;
	if(l<=tr[u].l && tr[u].r<=r) return tr[u].s;
	pushdown(u);
	return getsum(u<<1)+getsum(u<<1|1);
}
int main()
{
    n=read();
    m=read();
    for(ll i=1;i<=n;i++)
    {
        a[i]=read();
    }
    build(1,1,n);
    for(ll i=1;i<=m;i++)
    {
    	ll op=read();
    	l=read();
    	r=read();
    	if(op==1)
		{
			v=read();
			modify_add(1);
		}
		if(op==2)
		{
			v=read();
			modify_min(1);
		}
		if(op==3)
		{
			printf("%lld\n",getsum(1));
		}
		if(op==4)
		{
			printf("%lld\n",querymaxa(1));
		}
		if(op==5)
		{
			printf("%lld\n",querymaxb(1));
		}
    }
    return 0;
}

部分思路参照第一个题解

有一个点WA了

本人蒟蒻 在啃线段树