P1253 10pts求条

#include<bits/stdc++.h>
using namespace std;
int n,q,a[10000005];
struct node{
	int l,r,add,maxx,gai;
}tree[40000005];
void build(int p,int l,int r){
	tree[p].l=l,tree[p].r=r;
	if(tree[p].l==tree[p].r){
		tree[p].maxx=a[l];
		return;
	}
	int mid=(tree[p].l+tree[p].r)/2;
	build(2*p,l,mid);
	build(2*p+1,mid+1,r);
	tree[p].maxx=max(tree[2*p].maxx,tree[2*p+1].maxx);
}
void coverdown(int p){
	if(tree[p].gai!=0){
		tree[2*p].add=0;
		tree[2*p].gai=tree[p].gai;
		tree[2*p].maxx=tree[p].gai;
		tree[2*p+1].add=0;
		tree[2*p+1].gai=tree[p].gai;
		tree[2*p+1].maxx=tree[p].gai;
		tree[p].gai=0;
	}
}
void adddown(int p){
	coverdown(p);
	tree[2*p].maxx+=tree[p].add;
	tree[2*p].add+=tree[p].add;
	tree[2*p+1].maxx+=tree[p].add;
	tree[2*p+1].add+=tree[p].add;
	tree[p].add=0;
}
void cover(int p,int l,int r,int k){
	if(tree[p].l>=l&&tree[p].r<=r){
		tree[p].gai=k;
		tree[p].maxx=k;
		tree[p].add=0;
		return;
	}
	coverdown(p);
	int mid=(tree[p].l+tree[p].r)/2;
	if(l<=mid)cover(2*p,l,r,k);
	if(r>mid)cover(2*p+1,l,r,k);
	tree[p].maxx=max(tree[2*p].maxx,tree[2*p+1].maxx); 
}
void sum(int p,int l,int r,int k){
	if(tree[p].l>=l&&tree[p].r<=r){
		tree[p].add+=k;
		tree[p].maxx+=k;
		return;
	}
	adddown(p);
	int mid=(tree[p].l+tree[p].r)/2;
	if(l<=mid)sum(2*p,l,r,k);
	if(r>mid)sum(2*p+1,l,r,k);
	tree[p].maxx=max(tree[2*p].maxx,tree[2*p+1].maxx);
}
int ask(int p,int l,int r){
	if(tree[p].l>=l&&tree[p].r<=r){
		return tree[p].maxx;
	}
	int ans=-23459678;
	int mid=(tree[p].l+tree[p].r)/2;
	if(l<=mid)ans=max(ans,ask(2*p,l,r));
	if(r>mid)ans=max(ans,ask(2*p+1,l,r));
	return ans;
}
signed main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	int op,l,r,x;
	build(1,1,n);
	for(int i=1;i<=q;i++){
		cin>>op;
		if(op==1){
			cin>>l>>r>>x;
			cover(1,l,r,x);
		}
		else if(op==2){
			cin>>l>>r>>x;
			sum(1,l,r,x);
		}
		else{
			cin>>l>>r;
			printf("%lld\n",ask(1,l,r));
		}
	} 
	return 0;
}