题目

#include<bits/stdc++.h>
#define N 100005
#define int long long
using namespace std;
int sum[N*4],lazy1[N*4],n,m,a[N*4],b,x2,y2,k2,lazy2[N*4],vis1[N*4],vis2[N*4];
void pushup(int k){
 sum[k]=max(sum[k<<1],sum[k<<1|1]);
}
void add(int k,int x){
	sum[k]+=x;
	lazy1[k]=x;
	vis1[k]=1;
}
void Add(int k,int x){
	sum[k]=x;
	lazy2[k]=x;
	vis2[k]=1;
}
void build(int k,int l,int r){
	if(l==r){
		sum[k]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	pushup(k);
//	sum[k]max(sum[k<<1],sum[k<<1|1]);
}
void pushdown(int k){
	if(vis1[k]==0){
		return;
	}
	add(k<<1,lazy1[k]);
	add(k<<1|1,lazy1[k]);
	lazy1[k]=0;
	vis1[k]=0;
}
void Pushdown(int k){
	if(vis2[k]==0){
		return;
	}
	Add(k<<1,lazy2[k]);
	Add(k<<1|1,lazy2[k]);
	lazy2[k]=0;
	lazy1[k]=0;
	vis1[k]=0;
	vis2[k]=0;
}
void modify(int k,int l,int r,int x,int y,int v)
{
//	cout<<l<<" "<<r<<endl;
	if(r<x||l>y)return;
	if(l>=x&&r<=y)
	{
		add(k,v);
		return;
	}
	int mid=(l+r)/2;
	Pushdown(k);
	pushdown(k);
	modify(k<<1,l,mid,x,y,v);
	modify(k<<1|1,mid+1,r,x,y,v);
	pushup(k);
}
void Modify(int k,int l,int r,int x,int y,int v)
{
//	cout<<l<<" "<<r<<endl;
	if(r<x||l>y)return;
	if(l>=x&&r<=y)
	{
		Add(k,v);
		return;
	}
	int mid=(l+r)/2;
	Pushdown(k);
	pushdown(k);
	Modify(k<<1,l,mid,x,y,v);
	Modify(k<<1|1,mid+1,r,x,y,v);
	pushup(k);
}
int query(int k,int l,int r,int x,int y)
{
	if(l>=x&&r<=y)
	{
		return sum[k];
	}
	int mid=(l+r)/2,res=LONG_LONG_MIN;
	Pushdown(k);
	pushdown(k);
	pushup(k);
	if(x<=mid)
	{
		res=max(res,query(k<<1,l,mid,x,y));
	}
	if(mid<y)
	{
		res=max(res,query(k<<1|1,mid+1,r,x,y));
	}
	return res;
}
signed main()
{
	ios::sync_with_stdio(0);
    cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,1,n);
//	cout<<sum[1];
	for(int i=1;i<=m;i++)
	{
		cin>>b;
		if(b==1)
		{
			cin>>x2>>y2>>k2;
			Modify(1,1,n,x2,y2,k2);
		}
		else if(b==2)
		{
			cin>>x2>>y2>>k2;
			modify(1,1,n,x2,y2,k2);
		}
		else{
			cin>>x2>>y2;
			cout<<query(1,1,n,x2,y2)<<endl;
		}
	}
	return 0;
}

$悬赏关注$