题目样例最后一行输出19，其余正确 验证码SPFA祭

#include<bits/stdc++.h>
#define INF 2147483647
#define N (int)(5e5+3)
using namespace std;
int n,m;
struct node{
	long long s;
	int l,r,a,b,cnt,sec,lazy1,lazy2,lazy3,lazy4;
}seg[N<<2];
void pushup(int p){
	seg[p].s=seg[p<<1].s+seg[p<<1|1].s;
	seg[p].a=max(seg[p<<1].a,seg[p<<1|1].a);
	seg[p].b=max(seg[p<<1].b,seg[p<<1|1].b);
	if(seg[p<<1].a==seg[p<<1|1].a){
		seg[p].cnt=seg[p<<1].cnt+seg[p<<1|1].cnt;
		seg[p].sec=max(seg[p<<1].sec,seg[p<<1|1].sec);
	}
	if(seg[p<<1].a>seg[p<<1|1].a){
		seg[p].cnt=seg[p<<1].cnt;
		seg[p].sec=max(seg[p<<1].sec,seg[p<<1|1].a);
	}
	if(seg[p<<1].a<seg[p<<1|1].a){
		seg[p].cnt=seg[p<<1|1].cnt;
		seg[p].sec=max(seg[p<<1].a,seg[p<<1|1].sec);
	}
}
void build(int p,int l,int r){
	seg[p].l=l;
	seg[p].r=r;
	if(l==r){
		scanf("%lld",&seg[p].s);
		seg[p].a=seg[p].b=seg[p].s;
		seg[p].sec=-INF;
		return;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	pushup(p);
}
void update(int p,int k1,int k2,int k3,int k4){
	seg[p].s+=1ll*k1*seg[p].cnt+1ll*k2*(seg[p].r-seg[p].l+1-seg[p].cnt);
	seg[p].b=max(seg[p].b,seg[p].a+k3);
	seg[p].lazy3=max(seg[p].lazy3,seg[p].lazy1+k3);
	seg[p].lazy4=max(seg[p].lazy4,seg[p].lazy2+k3);
	seg[p].a+=k1;
	seg[p].lazy1+=k1;
	seg[p].lazy2+=k2;
	if(seg[p].sec!=-INF) seg[p].sec+=k2;
}
void pushdown(int p){
	int m=max(seg[p<<1].a,seg[p<<1|1].a);
	if(seg[p<<1].a==m) update(p<<1,seg[p].lazy1,seg[p].lazy2,seg[p].lazy3,seg[p].lazy4);
	else update(p<<1,seg[p].lazy2,seg[p].lazy2,seg[p].lazy4,seg[p].lazy4);
	if(seg[p<<1|1].a==m) update(p<<1|1,seg[p].lazy1,seg[p].lazy2,seg[p].lazy3,seg[p].lazy4);
	else update(p<<1|1,seg[p].lazy2,seg[p].lazy2,seg[p].lazy4,seg[p].lazy4);
	seg[p].lazy1=seg[p].lazy2=seg[p].lazy3=seg[p].lazy4=0;
}
void func1(int p,int l,int r,int k){
	if(l>seg[p].r||r<seg[p].l) return;
	if(l<=seg[p].l&&seg[p].r<=r){
		update(p,k,k,k,k);
		return;
	}
	pushdown(p);
	func1(p<<1,l,r,k);
	func1(p<<1|1,l,r,k);
	pushup(p);
}
void func2(int p,int l,int r,int k){
	if(l>seg[p].r||r<seg[p].l||k>=seg[p].a) return;
	if(l<=seg[p].l&&seg[p].r<=r&&k>seg[p].sec){
        update(p,k-seg[p].a,0,k-seg[p].a,0);
        return;
    }
	pushdown(p);
	func2(p<<1,l,r,k);
    func2(p<<1|1,l,r,k);
	pushup(p);
}
long long func3(int p,int l,int r){
	if(l>seg[p].r||r<seg[p].l) return 0;
	if(l<=seg[p].l&&seg[p].r<=r) return seg[p].s;
	pushdown(p);
	return func3(p<<1,l,r)+func3(p<<1|1,l,r);
}
int func4(int p,int l,int r){
	if(l>seg[p].r||r<seg[p].l) return -INF;
	if(l<=seg[p].l&&seg[p].r<=r) return seg[p].a;
	pushdown(p);
	return max(func4(p<<1,l,r),func4(p<<1|1,l,r));
}
int func5(int p,int l,int r){
	if(l>seg[p].r||r<seg[p].l) return -INF;
	if(l<=seg[p].l&&seg[p].r<=r) return seg[p].b;
	pushdown(p);
	return max(func5(p<<1,l,r),func5(p<<1|1,l,r));
}
int main(){
	scanf("%d%d",&n,&m);
	build(1,1,n);
	while(m--){
		int f,l,r,k;
		scanf("%d%d%d",&f,&l,&r);
		if(f==1){
			scanf("%d",&k);
			func1(1,l,r,k);
		}
		if(f==2){
			scanf("%d",&k);
			func2(1,l,r,k);
		}
		if(f==3) printf("%lld\n",func3(1,l,r));
		if(f==4) printf("%d\n",func4(1,l,r));
		if(f==5) printf("%d\n",func5(1,l,r));
	}
    return 0;
}