线段树 20 pts 求调

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e6+5;
ll A[N],n,m;
struct tree {
	ll l,r,s,t_1,t_2=-INT_MAX;
#define l(x) t[x].l
#define r(x) t[x].r
#define s(x) t[x].s
#define t_1(x) t[x].t_1
#define t_2(x) t[x].t_2
} t[N<<2]; 
inline void build(ll k,ll l,ll r) {
	l(k)=l,r(k)=r;
	if(l==r) {
		s(k)=A[l];
		return;
	} ll mid=(l+r)/2;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	s(k)=max(s(k<<1),s(k<<1|1));
} inline void pushdown(ll k) {
	if(t_2(k)!=-INT_MAX) {
		t_2(k<<1)=t_2(k),t_2(k<<1|1)=t_2(k);
		s(k<<1)=(r(k<<1)-l(k<<1)+1)*t_2(k);
		s(k<<1|1)=(r(k<<1|1)-l(k<<1|1)+1)*t_2(k);
		t_2(k)=-INT_MAX; 
	} t_1(k<<1)+=t_1(k),t_1(k<<1|1)+=t_1(k);
	s(k<<1)+=(r(k<<1)-l(k<<1)+1)*t_1(k);
	s(k<<1|1)+=(r(k<<1|1)-l(k<<1|1)+1)*t_1(k);
	t_1(k)=0; 
} inline void Add(ll k,ll l,ll r,ll v) {
	if(l<=l(k)&&r(k)<=r) {
		s(k)+=(r(k)-l(k)+1)*v;
		t_1(k)+=v; return;
	} if(r<l(k)||r(k)<l) return;
	pushdown(k);
	Add(k<<1,l,r,v),Add(k<<1|1,l,r,v);
	s(k)=max(s(k<<1),s(k<<1|1));
} inline ll MAX(ll k,ll l,ll r) {
	if(l<=l(k)&&r(k)<=r) return s(k);
	if(r<l(k)||r(k)<l) return -INT_MAX;
	pushdown(k);
	return max(MAX(k<<1,l,r),MAX(k<<1|1,l,r));
} inline void Change(int k,int l,int r,int v) {
	if(l<=l(k)&&r(k)<=r) {
		s(k)=(r(k)-l(k)+1)*v;
		t_2(k)=v; t_1(k)=0; return;
	} if(r<l(k)||r(k)<l) return;
	pushdown(k);
	Change(k<<1,l,r,v),Change(k<<1|1,l,r,v);
	s(k)=max(s(k<<1),s(k<<1|1));
} int main() {
	ios::sync_with_stdio(0);
	cout.tie(0); cin.tie(0);
	cin>>n>>m;
	for(ll i=1;i<=n;i++) cin>>A[i];
	build(1,1,n);
	for(int i=1;i<=m;i++) {
		ll op,x,y,k;
		cin>>op>>x>>y;
		if(op==1) cin>>k,Change(1,x,y,k);
		if(op==2) cin>>k,Add(1,x,y,k);
		if(op==3) cout<<MAX(1,x,y)<<'\n';
	} return 0;
}