题目

60分代码：

#include<bits/stdc++.h>
using namespace std;
const long long N=1e7+10,inf=1e18;
long long a[N*4],tree[N*4],tag[N*4],tag2[N*4],n,m;
long long ls(long long p){return (p<<1);}
long long rs(long long p){return (p<<1|1);}
void update(long long p)
{
	tree[p]=max(tree[ls(p)],tree[rs(p)]);
}
void build(long long p,long long pl,long long pr)
{
	tag2[p]=inf;
	if(pl==pr)
	{
		tree[p]=a[pl];
		return;
	}
	long long mid=(pl+pr)>>1;
	build(ls(p),pl,mid);
	build(rs(p),mid+1,pr);
	update(p);
}
void tag_down(long long p)
{
	tag[ls(p)]+=tag[p];
	tree[ls(p)]+=tag[p];
	tag[rs(p)]+=tag[p];
	tree[rs(p)]+=tag[p];
	tag[p]=0;
}
void tag_down2(long long p)
{
	if(tag2[p]!=inf)
	{
		tag2[ls(p)]=tag2[p];
		tag[ls(p)]=0;
		tree[ls(p)]=tag2[p];
		tag2[rs(p)]=tag2[p];
		tag[rs(p)]=0;
		tree[rs(p)]=tag2[p];
		tag[p]=0;
		tag2[p]=inf;
	}
}
void change(long long l,long long r,long long p,long long pl,long long pr,long long d)
{
	if(l<=pl&&pr<=r)
	{
		tag[p]+=d;
		tree[p]+=d;
		return;
	}
	tag_down2(p);
	tag_down(p);
	long long mid=(pl+pr)>>1;
	if(l<=mid)
	{
		change(l,r,ls(p),pl,mid,d);
	}
	if(r>mid)
	{
		change(l,r,rs(p),mid+1,pr,d);
	}
	update(p);
}
void change2(long long l,long long r,long long p,long long pl,long long pr,long long d)
{
	if(l<=pl&&pr<=r)
	{
		tag2[p]=d;
		tree[p]=d;
		tag[p]=0;
		return;
	}
	tag_down2(p);
	tag_down(p);
	long long mid=(pl+pr)>>1;
	if(l<=mid)
	{
		change2(l,r,ls(p),pl,mid,d);
	}
	if(r>mid)
	{
		change2(l,r,rs(p),mid+1,pr,d);
	}
	update(p);
}
long long sum(long long l,long long r,long long p,long long pl,long long pr)
{
	if(l<=pl&&pr<=r)
	{
		return tree[p];
	}
	tag_down2(p);
	tag_down(p);
	long long res=-1e18,mid=(pl+pr)>>1;
	if(l<=mid)
	{
		res=max(res,sum(l,r,ls(p),pl,mid));
	}
	if(r>mid)
	{
		res=max(res,sum(l,r,rs(p),mid+1,pr));
	}
	return res;
}
int main()
{
	cin>>n>>m;
	for(long long i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]); 
	}
	build(1,1,n);
	while(m--)
	{
		long long q,l,r,d;
		scanf("%lld%lld%lld",&q,&l,&r); 
		if(q==1)
		{
			scanf("%lld",&d); 
			change2(l,r,1,1,n,d);
		}
		if(q==2)
		{
			scanf("%lld",&d); 
			change(l,r,1,1,n,d);
		}
		if(q==3)
		{
			cout<<sum(l,r,1,1,n)<<"\n";
		}
	}
	return 0;
}

改了两天，红了.......

提交记录