P1253 扶苏的问题

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[1000005],x,y,z,k;
struct t
{
	long long l,r,lazy,mx=INT_MIN,change;
	bool use;
}t[4000005];
void build(long long l,long long r,long long g)
{
	t[g].l=l,t[g].r=r;
	if(l==r)
	{
		t[g].mx=a[l];
		return;
	}
	long long mid=l+r>>1;
	build(l,mid,g*2);
	build(mid+1,r,g*2+1);
	t[g].mx=max(t[g*2].mx,t[g*2+1].mx);
}
void down(long long g)
{
	if(t[g].use)
	{
		long long l=g*2,r=g*2+1;
		t[l].change=t[g].change;
		t[r].change=t[g].change;
		t[l].lazy=t[g].lazy;
		t[r].lazy=t[g].lazy; 
		t[l].mx=t[g].change+t[g].lazy;
		t[r].mx=t[g].change+t[g].lazy;
	}else
	{
		long long l=g*2,r=g*2+1;
		t[l].lazy+=t[g].lazy;
		t[r].lazy+=t[g].lazy;
		t[l].mx+=t[g].lazy;
		t[r].mx+=t[g].lazy;
	}
	t[g].use=t[g].change=t[g].lazy=0;
	return;
}
void change(long long g,long long l,long long r,long long sum)
{
	if(t[g].r<l||t[g].l>r)
	  return;
	if(t[g].l>=l&&t[g].r<=r)
	{
		t[g].lazy=0;
		t[g].mx=sum;
		t[g].change=sum;
		t[g].use=true;
		return;
	}
	down(g);
	change(g*2,l,r,sum);
	change(g*2+1,l,r,sum);
	t[g].mx=max(t[g*2].mx,t[g*2+1].mx);
	return;
}
void add(long long g,long long l,long long r,long long sum)
{
	if(t[g].r<l||t[g].l>r)
	  return;
	t[g].change=0;
	if(t[g].l>=l&&t[g].r<=r)
	{
		t[g].mx+=sum;
		t[g].lazy+=sum;
		return;
	}
	down(g);
	add(g*2,l,r,sum);
	add(g*2+1,l,r,sum);
	t[g].mx=max(t[g*2].mx,t[g*2+1].mx);
	return;
}
long long ask(long long g,long long l,long long r)
{
	if(t[g].r<l||t[g].l>r)
	{
		return INT_MIN;
	}
	if(t[g].l>=l&&t[g].r<=r)
	{
		return t[g].mx;
	}
	down(g);
	long long ans=max(ask(g*2,l,r),ask(g*2+1,l,r));
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(long long i=1;i<=n;++i)
	  cin>>a[i];
	build(1,n,1);
	while(m--)
	{
		cin>>k;
		if(k==1)
		{
			cin>>x>>y>>z;
			change(1,x,y,z);
		}else
			if(k==2)
			{
				cin>>x>>y>>z;
				add(1,x,y,z);
			}else
				{
					cin>>x>>y;
					cout<<ask(1,x,y)<<'\n';
				}
	}
}

50分求助QwQ