50pts线段树求条

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <queue>
#include <vector>
using namespace std;

#define int long long
#define maxn 1000005
#define none -1145141919180

inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}

int n,q;
int val[maxn];
int sum[maxn];
int clr[maxn];
int www[maxn];
int nowl,nowr;
int opt;

void update(int rt){
	sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
	return;
}//更新（建树）

void build(int l,int r,int rt){
	if(l==r){
		sum[rt]=val[l];
		www[rt]=none;
		clr[rt]=0;
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	update(rt);
}//建树

void color1(int l,int r,int rt,int val){
	clr[rt]=0;
	www[rt]=val+clr[rt];
	sum[rt]=www[rt];
	return;
}//opt 1 的标记

void push_color1(int l,int r,int rt){
	if(www[rt]!=none){
		int mid=(l+r)>>1;
		color1(l,mid,rt<<1,www[rt]);
		color1(mid+1,r,rt<<1|1,www[rt]);
		www[rt]=none;
	}
	return;
}//下放标记

void change1(int l,int r,int rt,int x){
	if(l>=nowl&&r<=nowr){
		color1(l,r,rt,x);
		return;
	}
	push_color1(l,r,rt);
	int mid=(l+r)>>1;
	if(mid>=nowl) change1(l,mid,rt<<1,x);
	if(mid+1<=nowr) change1(mid+1,r,rt<<1|1,x);
	update(rt);
	return;
}//opt1 操作

void color2(int l,int r,int rt,int c){
	sum[rt]=sum[rt]+c;
	clr[rt]+=c;
	return;	
}//opt 2 标记

void push_color2(int l,int r,int rt){
	if(clr[rt]){
		int mid=(l+r)>>1;
		color2(l,mid,rt<<1,clr[rt]);
		color2(mid+1,r,rt<<1|1,clr[rt]);
		clr[rt]=0;
	}
	return;
}//下放

void change2(int l,int r,int rt,int x){
	if(l>=nowl&&r<=nowr){
		color2(l,r,rt,x);
		return;
	}
	push_color2(l,r,rt);
	int mid=(l+r)>>1;
	if(mid>=nowl) change2(l,mid,rt<<1,x);
	if(mid+1<=nowr) change2(mid+1,r,rt<<1|1,x);
	update(rt);
	return;
}//更改 opt 2

int find(int l,int r,int rt){
	int ans=-1;
	if(l>=nowl&&r<=nowr){
		return sum[rt];
	}
	int mid=(l+r)>>1;
	push_color2(l,r,rt);
	push_color2(l,r,rt);
	if(mid>=nowl){
		int fff=find(l,mid,rt<<1); 
		ans=max(fff,ans);
	}
	if(mid+1<=nowr){
		int fff=find(mid+1,r,rt<<1|1); 
		ans=max(fff,ans);
	}
	return ans;
}//查询

signed main(){
	n=read();q=read();
	for(int i=1;i<=n;++i){
		val[i]=read();
	}
	build(1,n,1);
	for(int i=1;i<=q;++i){
		opt=read();
		if(opt==1){
			int x;
			nowl=read();nowr=read();x=read();
			change1(1,n,1,x);
		}
		else if(opt==2){
			int x;
			nowl=read();nowr=read();x=read();
			change2(1,n,1,x);
		}
		else{
			nowl=read();nowr=read();
			cout<<find(1,n,1)<<endl;
		}
	}
	return 0;
}