ACon1 5 6，求条

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
const int INF=1e16;
#define ls p*2
#define rs p*2+1
int a[N];
struct T
{
	int sum,st,nd,his,num;//和，最大值，严格次大值，历史最大值，最大值次数 
	int l,r;
	int tag1,tag2,tag3,tag4;
	void clear()
	{
		tag1=tag2=tag3=tag4=0;
	}
}t[N<<2];
void pushup(int p)
{
	t[p].st=max(t[ls].st,t[rs].st);
	t[p].his=max(t[ls].his,t[rs].his);
	t[p].sum=t[ls].sum+t[rs].sum;
	if(t[ls].st==t[rs].st)
	{
		t[p].nd=max(t[ls].nd,t[rs].nd);
		t[p].num=(t[ls].num+t[rs].num);
	}
	else if(t[ls].st>t[rs].st)
	{
		t[p].nd=max(t[ls].nd,t[rs].st);
		t[p].num=t[ls].num;
	}
	else
	{
		t[p].nd=max(t[ls].st,t[rs].nd);
		t[p].num=t[rs].num;
	}
	return ;
}
void build(int p,int l,int r)
{
	t[p].l=l,t[p].r=r;
	t[p].clear();
	if(l==r)
	{
		t[p].sum=t[p].st=t[p].his=a[l];
		t[p].nd=-INF;
		t[p].num=1;
		return ; 
	}
	int mid=(l+r)/2;
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(p);
	return ;
}
void update(int p,int l1,int l2,int l3,int l4)
{
	t[p].sum+=(l1*t[p].num+l3*(t[p].r-t[p].l+1-t[p].num));
	t[p].his=max(t[p].his,t[p].st+l2);
	t[p].st+=l1;
	if(t[p].nd!=-INF) t[p].nd+=l3;
	t[p].tag2=max(t[p].tag2,t[p].tag1+l2);
	t[p].tag1+=l1;
	t[p].tag4=max(t[p].tag4,t[p].tag3+l4);
	t[p].tag3+=l3;
	return ;
}
void pushdown(int p)
{
	int ma=max(t[ls].st,t[rs].st);
	if(t[ls].st==ma) update(ls,t[p].tag1,t[p].tag2,t[p].tag3,t[p].tag4);
	else update(ls,t[p].tag3,t[p].tag4,t[p].tag3,t[p].tag4);
	if(t[rs].st==ma) update(rs,t[p].tag1,t[p].tag2,t[p].tag3,t[p].tag4);
	else update(rs,t[p].tag3,t[p].tag4,t[p].tag3,t[p].tag4);
	t[p].clear();
	return ;
}
void modify1(int p,int l,int r,int k)
{
	if(t[p].l>r||t[p].r<l) return ;
	if(t[p].l>=l&&t[p].r<=r)
	{
		update(p,k,k,k,k);
		return ;
	}
	pushdown(p);
	modify1(ls,l,r,k);
	modify1(rs,l,r,k);
	pushup(p);
	return ;
}
void modify2(int p,int l,int r,int k)
{
	if(t[p].l>r||t[p].r<l) return ;
	if(t[p].l>=l&&t[p].r<=r&&t[p].nd<k)
	{
		update(p,k-t[p].st,k-t[p].st,0,0);
		return ;
	}
	pushdown(p);
	modify2(ls,l,r,k);
	modify2(rs,l,r,k);
	pushup(p);
	return ;
}
int query1(int p,int l,int r)
{
	if(t[p].l>r||t[p].r<l) return 0;
	if(t[p].l>=l&&t[p].r<=r) return t[p].sum;
	pushdown(p);
	int ans=0;
	ans+=query1(ls,l,r);
	ans+=query1(rs,l,r);
	return ans;
}
int query2(int p,int l,int r)
{
	if(t[p].l>r||t[p].r<l) return -INF;
	if(t[p].l>=l&&t[p].r<=r) return t[p].st;
	pushdown(p);
	int ans=-INF;
	ans=max(ans,query2(ls,l,r));
	ans=max(ans,query2(rs,l,r));
	return ans;
}
int query3(int p,int l,int r)
{
	if(t[p].l>r||t[p].r<l) return -INF;
	if(t[p].l>=l&&t[p].r<=r) return t[p].his;
	pushdown(p);
	int ans=-INF;
	ans=max(ans,query3(ls,l,r));
	ans=max(ans,query3(rs,l,r));
	return ans;
}
signed main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int l,r,k;
			cin>>l>>r>>k;
			modify1(1,l,r,k);
		}
		else if(op==2)
		{
			int l,r,v;
			cin>>l>>r>>v;
			modify2(1,l,r,v);
		}
		else if(op==3)
		{
			int l,r;
			cin>>l>>r;
			cout<<query1(1,l,r)<<endl;
		}
		else if(op==4)
		{
			int l,r;
			cin>>l>>r;
			cout<<query2(1,l,r)<<endl;
		}
		else
		{
			int l,r;
			cin>>l>>r;
			cout<<query3(1,l,r)<<endl;
		}
	}
	return 0;
}