20分求条，ACon#1#3

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define itn int
const int N = 1e6+5;
const long long sb = -1145678278379;
int n,q;
struct node{
	int l,r;
	ll maxn,c_tag,a_tag;
}a[4*N];
int c[N];
inline int ls(int x){
	return x<<1;
}
inline int rs(itn x){
	return x<<1|1;
}
inline push_up(int x){
	a[x].maxn = max(a[ls(x)].maxn,a[rs(x)].maxn);
}
inline push_down_c(int x){
	if(a[x].c_tag!=sb){
		a[ls(x)].maxn = a[x].c_tag;
		a[rs(x)].maxn = a[x].c_tag;
		a[ls(x)].c_tag = a[x].c_tag;
		a[rs(x)].c_tag = a[x].c_tag;
		a[ls(x)].a_tag = 0;
		a[rs(x)].a_tag = 0;
		a[x].c_tag = sb;
	}
}
inline push_down_a(int x){
	if(a[x].a_tag){
		a[ls(x)].a_tag = a[x].a_tag;
		a[rs(x)].a_tag = a[x].a_tag;
		a[ls(x)].maxn+=a[x].a_tag;
		a[rs(x)].maxn+=a[x].a_tag;
		a[x].a_tag = 0;
	}
}
inline void push_down(int x){
	push_down_c(x),push_down_a(x);
}
void build(int x,int l,int r){
	a[x].l = l,a[x].r = r;
	a[x].c_tag = sb;
	if(l==r){
		a[x].maxn = c[l];
		return;
	}
	int mid = (l+r)>>1;
	build(ls(x),l,mid);
	build(rs(x),mid+1,r);
	push_up(x);
}
void update_a(int x,int l,int r,int v){
	if(l<=a[x].l&&a[x].r<=r){
		a[x].maxn+=v;
		a[x].a_tag+=v;
		push_down_a(x);
		return;
	}
	push_down(x);
	int mid = (a[x].l+a[x].r)>>1;
	if(l<=mid)update_a(ls(x),l,mid,v);
	if(r>mid)update_a(rs(x),mid+1,r,v);
	push_up(x);
}
void update_c(int x,int l,int r,int v){
	if(l<=a[x].l&&a[x].r<=r){
		a[x].maxn=v;
		a[x].c_tag=v;
		return;
	}
	push_down(x);
	int mid = (a[x].l+a[x].r)>>1;
	if(l<=mid)update_c(ls(x),l,mid,v);
	if(r>mid)update_c(rs(x),mid+1,r,v);
	push_up(x);
}
ll query(int x,int l,int r){
	if(l<=a[x].l&&a[x].r<=r){
		return a[x].maxn;
	}
	push_down(x);
	int mid = (a[x].l+a[x].r)>>1;
	ll res = 0;
	if(l<=mid)res+=query(ls(x),l,r);
	if(r>mid)res+=query(rs(x),l,r);
	return res;
}
void solve(){
	int op,l,r;
	cin>>op>>l>>r;
	if(op==1){
		int x;
		cin>>x;
		update_c(1,l,r,x);
	}
	if(op==2){
		int x;
		cin>>x;
		update_a(1,l,r,x);
	}
	if(op==3){
		cout<<query(1,l,r)<<"\n";
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i = 1;i<=n;i++){
		cin>>c[i];
	}
	build(1,1,n);
	while(q--)solve();
	return 0;
}