rt
线段树做法
$s$维护区间最大值
$t_{1}$是区间赋值的懒标记
$t_{2}$是区间加的懒标记
评测记录 原题链接

#include<bits/stdc++.h>
#define int long long
#define ls (p<<1)
#define rs ((p<<1)+1)
#define mid ((l+r)>>1)
using namespace std;
const int N=1000005;
const int inf=1e18;
int n,q,i,a[N],op,l,r,x;
struct sqt
{
	int s[N*4],t1[N*4],t2[N*4];
	void pushup(int p)
	{
		s[p]=max(s[ls],s[rs]);
	}
	void addtag1(int p,int x)
	{
		s[p]=x;
		t2[p]=0;
		t1[p]=x;
	}
	void addtag2(int p,int x)
	{
		s[p]+=x;
		t2[p]+=x;
	}
	void pushdown(int p)
	{
		if(t1[p])
		{
			addtag1(ls,t1[p]);
			addtag1(rs,t1[p]);
			t1[p]=0;
		}
		if(t2[p])
		{
			addtag2(ls,t2[p]);
			addtag2(rs,t2[p]);
			t2[p]=0;
		}
	}
	void build(int p,int l,int r)
	{
		if(l==r)
		{
			s[p]=a[l];
			return;
		}
		build(ls,l,mid);
		build(rs,mid+1,r);
		pushup(p);
	}
	void chg(int p,int l,int r,int L,int R,int x)
	{
		if(R<l||L>r) return;
		if(L<=l&&r<=R) return addtag1(p,x);
		pushdown(p);
		chg(ls,l,mid,L,R,x);
		chg(rs,mid+1,r,L,R,x);
		pushup(p);
	}
	void add(int p,int l,int r,int L,int R,int x)
	{
		if(R<l||L>r) return;
		if(L<=l&&r<=R) return addtag2(p,x);
		pushdown(p);
		add(ls,l,mid,L,R,x);
		add(rs,mid+1,r,L,R,x);
		pushup(p);
	}
	int ask(int p,int l,int r,int L,int R)
	{
		if(R<l||L>r) return (inf*(-1));
		if(L<=l&&r<=R) return s[p];
		pushdown(p);
		return max(ask(ls,l,mid,L,R),ask(rs,mid+1,r,L,R));
	}
}xds;
signed main()
{
	ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
	cin>>n>>q;
	for(i=1;i<=n;i++) cin>>a[i];
	xds.build(1,1,n);
	while(q--)
	{
		cin>>op;
		if(op==1)
		{
			cin>>l>>r>>x;
			xds.chg(1,1,n,l,r,x);
		}
		if(op==2)
		{
			cin>>l>>r>>x;
			xds.add(1,1,n,l,r,x);
		}
		if(op==3)
		{
			cin>>l>>r;
			cout<<xds.ask(1,1,n,l,r)<<'\n';
		}
	}
	return 0;
}