https://www.luogu.com.cn/record/199005414

#include<bits/stdc++.h>
using namespace std;
const int N=500010;
long long a[N];
int n,m;
struct node1{long long val,his,sum,sz;};
struct node2{long long tag1,tag2;};
node1 tree[N<<2];node2 lazy[N<<2];
inline node1 operator+(node1 a,node1 b){return{max(a.val,b.val),max(a.his,b.his),a.sum+b.sum,a.sz+b.sz};}
inline node2 operator*(node2 a,node2 b){return{a.tag1+b.tag1,max(a.tag2,a.tag1+b.tag2)};}
inline node1 operator*(node1 a,node2 b){return{a.val+b.tag1,a.his+b.tag2,a.sum+a.sz*b.tag1,a.sz};}
void build(int k,int l,int r){
	if(l==r){tree[k]={a[l],a[l],a[l],1};return;}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	tree[k]=tree[k<<1]+tree[k<<1|1];
}
void pushdown(int k){
	tree[k<<1]=tree[k<<1]*lazy[k];
	tree[k<<1|1]=tree[k<<1|1]*lazy[k];
	lazy[k<<1]=lazy[k<<1]*lazy[k];
	lazy[k<<1|1]=lazy[k<<1|1]*lazy[k];
	lazy[k]={0,0};
}
void update(int k,int l,int r,int x,int y,node2 v){
	if(l>y||r<x)	return;
	if(l>=x&&r<=y){
		tree[k]=tree[k]*v;
		lazy[k]=lazy[k]*v;
		return;
	}
	pushdown(k);
	int mid=(l+r)>>1;
	update(k<<1,l,mid,x,y,v);
	update(k<<1|1,mid+1,r,x,y,v);
	tree[k]=tree[k<<1]+tree[k<<1|1];
}
node1 query(int k,int l,int r,int x,int y){
	if(l>=x&&r<=y)	return tree[k];
	pushdown(k);
	int mid=(l+r)>>1;
	if(y<=mid)	return query(k<<1,l,mid,x,y);
	if(x>mid)	return query(k<<1|1,mid+1,r,x,y);
	return query(k<<1,l,mid,x,y)+query(k<<1|1,mid+1,r,x,y);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)	scanf("%lld",&a[i]);
	build(1,1,n);
	while(m--){
		int op,l,r;scanf("%d%d%d",&op,&l,&r);
		if(op==1){
			long long k;scanf("%lld",&k);
			update(1,1,n,l,r,{k,max(k,0ll)});
		}
		if(op==2){
			long long k;scanf("%lld",&k);
		}
		if(op==3)	printf("%lld\n",query(1,1,n,l,r).sum);
		if(op==4)	printf("%lld\n",query(1,1,n,l,r).val);
		if(op==5)	printf("%lld\n",query(1,1,n,l,r).his);
	}
	return 0;
}