线段树40pts求调

#include <cstdio>
#define int long long

using namespace std;
template<typename T>
inline void in (T &x) {char c;int f=1;do {c=getchar ();if (c=='-') f=-1;} while (c>'9' || c<'0');for (x=0;c>='0' && c<='9';c=getchar ()) x=(x<<1)+(x<<3)+(c^48);x*=f;}
template<typename T>
inline void out (T x,char c) {if (x==0) {putchar ('0'),putchar (c); return ;}if (x<0) putchar ('-'),x=-x;int sta[20],k=0;while (x) sta[++k]=x%10,x/=10;while (k) putchar (sta[k--]+'0');putchar (c);}

const int N=1e6+10,oo=1<<60;
struct Segement {
	int l,r;
	int sum,alz,clz;
}tr[N<<2];
int a[N];
int n,q;
int op,x,y,k;

inline int max (const int &p,const int &q) {return p>q?p:q;}
inline void push_up (int p) {tr[p].sum=max (tr[p<<1].sum,tr[p<<1|1].sum);}
inline void c_push_down (int p) {
	if (tr[p].clz!=-oo) {
		tr[p<<1].alz=tr[p<<1|1].alz=0;
		tr[p<<1].clz=tr[p<<1|1].clz=tr[p].clz;
		tr[p<<1].sum=tr[p<<1|1].sum=tr[p].clz;
		tr[p].clz=-oo;
	}
}
inline void a_push_down (int p) {
	if (tr[p].alz) {
		c_push_down (p);
		tr[p<<1].sum+=tr[p].alz,tr[p<<1|1].sum+=tr[p].alz;
		tr[p<<1].alz+=tr[p].alz,tr[p<<1|1].alz+=tr[p].alz;
		tr[p].alz=0;
	}
}
inline void push_down (int p) {c_push_down (p),a_push_down (p);}
inline void build (int p,int l,int r) {
	tr[p].l=l,tr[p].r=r;
	if (l==r) {tr[p].sum=a[l],tr[p].clz=-oo,tr[p].alz=0; return ;}
	int mid=(l+r)/2;
	build (p<<1,l,mid);
	build (p<<1|1,mid+1,r);
	push_up (p);
}
inline void cmodify (int p,int l,int r,int k) {
	if (tr[p].l>=l && tr[p].r<=r) {tr[p].sum=k,tr[p].alz=0,tr[p].clz=k; return ;}
	push_down (p);
	if (tr[p<<1].r>=l) cmodify (p<<1,l,r,k);
	if (tr[p<<1|1].l<=r) cmodify (p<<1|1,l,r,k);
	push_up (p);
}
inline void amodify (int p,int l,int r,int k) {
	if (tr[p].l>=l && tr[p].r<=r) {
		c_push_down (p);
		tr[p].sum+=k,tr[p].alz+=k; 
		return ;
	}
	push_down (p);
	if (tr[p<<1].r>=l) amodify (p<<1,l,r,k);
	if (tr[p<<1|1].l<=r) amodify (p<<1|1,l,r,k);
	push_up (p);
}
inline int query (int p,int l,int r) {
	if (tr[p].l>=l && tr[p].r<=r) return tr[p].sum;
	push_down (p);
	int s=-oo;
	if (tr[p<<1].r>=l) s=max (s,query (p<<1,l,r));
	if (tr[p<<1|1].l<=r) s=max (s,query (p<<1|1,l,r));
	return s;
}
signed main () {
	in (n),in (q);
	for (int i=1;i<=n;++i) in (a[i]);
	build (1,1,n);
	for (int i=1;i<=n*4;++i) tr[i].clz=-oo;
	for (;q--;) {
		in (op);
		if (op==1) {in (x),in (y),in (k); cmodify (1,x,y,k);}
		if (op==2) {in (x),in (y),in (k); amodify (1,x,y,k);}
		if (op==3) {in (x),in (y); out (query (1,x,y),'\n');} 
	}
	return 0;
}