#include <bits/stdc++.h>
namespace IO{
	#define LL long long
	inline LL read(){
		LL x=0,f=1;char c=getchar();
		for (;!isdigit(c);c=getchar())if (c=='-')f=-1;
		for (;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
		return x*f;
	}
	inline void write(LL x,char c='\n'){
		if (x){
			if (x<0)x=-x,putchar('-');
			char a[30];short l;
			for (l=0;x;x/=10)a[l++]=x%10^48;
			for (l--;l>=0;l--)putchar(a[l]);
		}else putchar('0');putchar(c);
	}
}using namespace IO;
using namespace std;

#define int long long
const int N = 2e6+10;
struct Tree{int l,r,sum,maxa,maxb,sec,cnt,tag1,tag2,tag3,tag4;};
Tree tree[N];int opt,l,r,k,v,n,m;
inline int ls(int now){return now<<1;}
inline int rs(int now){return now<<1|1;}
inline void pushup(int now){
	tree[now].sum=tree[ls(now)].sum+tree[rs(now)].sum;
	tree[now].maxa=max(tree[ls(now)].maxa,tree[rs(now)].maxa);
	tree[now].maxb=max(tree[ls(now)].maxb,tree[rs(now)].maxb);
	if (tree[ls(now)].maxa==tree[rs(now)].maxa)
		tree[now].sec=max(tree[ls(now)].sec,tree[rs(now)].sec),
		tree[now].cnt=tree[ls(now)].cnt+tree[rs(now)].cnt;
	else if (tree[ls(now)].maxa>tree[rs(now)].maxa)
		tree[now].sec=max(tree[ls(now)].sec,tree[rs(now)].maxa),
		tree[now].cnt=tree[ls(now)].cnt;
	else
		tree[now].sec=max(tree[ls(now)].maxa,tree[rs(now)].sec),
		tree[now].cnt=tree[rs(now)].cnt;
}
void build(int now,int l,int r){
	tree[now].l=l,tree[now].r=r;
	if (l==r){
		tree[now].sum=tree[now].maxa=tree[now].maxb=read();
		tree[now].cnt=1;
		tree[now].sec=-2e9;
		return;
	}
	int mid=(l+r)>>1;
	build(ls(now),l,mid);
	build(rs(now),mid+1,r);
	pushup(now);
}
inline void add_lazytag(int now,int tag1,int tag2,int tag3,int tag4){
	tree[now].sum+=tag1*tree[now].cnt+tag2*(tree[now].r-tree[now].l+1-tree[now].cnt);
	tree[now].maxb=max(tree[now].maxb,tree[now].maxa+tag3);
	tree[now].maxa+=tag1;
	if (tree[now].sec!=-2e9)tree[now].sec+=tag2;
	tree[now].tag3=max(tree[now].tag3,tree[now].tag1+tag3);
	tree[now].tag4=max(tree[now].tag4,tree[now].tag2+tag4);
	tree[now].tag1+=tag1;
	tree[now].tag2+=tag2;
}
inline void pushdown(int now){
	int ma=max(tree[ls(now)].maxa,tree[rs(now)].maxa);
	if (tree[ls(now)].maxa==ma)
		add_lazytag(ls(now),tree[now].tag1,tree[now].tag2,tree[now].tag3,tree[now].tag4);
	else
		add_lazytag(ls(now),tree[now].tag2,tree[now].tag2,tree[now].tag4,tree[now].tag4);
	if (tree[rs(now)].maxa==ma)
		add_lazytag(rs(now),tree[now].tag1,tree[now].tag2,tree[now].tag3,tree[now].tag4);
	else
		add_lazytag(rs(now),tree[now].tag2,tree[now].tag2,tree[now].tag4,tree[now].tag4);
	tree[now].tag1=tree[now].tag2=tree[now].tag3=tree[now].tag4=0;	
}
void update_add(int now){
	if (l>tree[now].r||r<tree[now].l)return;
	if (l<=tree[now].l&&tree[now].r<=r){
		tree[now].sum+=k*tree[now].cnt+k*(tree[now].r-tree[now].l+1-tree[now].cnt);
		tree[now].maxa+=k;
		tree[now].maxb=max(tree[now].maxb,tree[now].maxa);
		if (tree[now].sec!=-2e9)tree[now].sec+=k;
		tree[now].tag1+=k;
		tree[now].tag2+=k;
		tree[now].tag3=max(tree[now].tag3,tree[now].tag1);
		tree[now].tag3=max(tree[now].tag4,tree[now].tag2);
		return;
	}
	pushdown(now);
	update_add(ls(now));
	update_add(rs(now));
	pushup(now);
}
void update_min(int now){
	if (l>tree[now].r||r<tree[now].l||v>=tree[now].maxa)return;
	if (l<=tree[now].l&&tree[now].r<=r&&tree[now].sec<v){
		int tmp=tree[now].maxa-v;
		tree[now].sum-=tree[now].cnt*tmp;
		tree[now].maxa=v;
		tree[now].tag1-=tmp;
		return;
	}
	pushdown(now);
	update_min(ls(now));
	update_min(rs(now));
	pushup(now);
}
int query_sum(int now){
	if (l>tree[now].r||r<tree[now].l)return 0;
	if (l<=tree[now].l&&tree[now].r<=r)return tree[now].sum;
	pushdown(now);
	return query_sum(ls(now))+query_sum(rs(now));
}
int query_maxa(int now){
	if (l>tree[now].r||r<tree[now].l)return -2e9;
	if (l<=tree[now].l&&tree[now].r<=r)return tree[now].maxa;
	pushdown(now);
	return max(query_maxa(ls(now)),query_maxa(rs(now)));
}
int query_maxb(int now){
	if (l>tree[now].r||r<tree[now].l)return -2e9;
	if (l<=tree[now].l&&tree[now].r<=r)return tree[now].maxb;
	pushdown(now);
	return max(query_maxb(ls(now)),query_maxb(rs(now)));
}
signed main(){
	n=read(),m=read();
	build(1,1,n);
	for (int i=1;i<=m;i++){
		opt=read(),l=read(),r=read();
		if (opt==1)k=read(),update_add(1);
		if (opt==2)v=read(),update_min(1);
		if (opt==3)write(query_sum(1));
		if (opt==4)write(query_maxa(1));
		if (opt==5)write(query_maxb(1));
	}
	return 0;
}

悬赏 1 关注