RT，参考了第二篇题解。

好像不修改前的询问都是对的，估计是修改锅了（）

//#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int N = 5e5 + 10, inf = 2e9 + 1207;
int n, m, a[N];
inline ll read(){
	ll x = 0, m = 1;
	char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') m = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * m;
}
inline void write(ll x){
	if(x < 0){
		putchar('-');
		write(-x);
		return;
	}
	if(x >= 10) write(x / 10);
	putchar(x % 10 + '0');
}
struct Tree{
	int l, r, sum, cnt;
	int max, all_max, se;
	int add1, add1_, add2, add2_;
}tree[N << 2];
inline void update(int k1, int k1_, int k2, int k2_, int sum){
	tree[sum].sum += (k1 * tree[sum].cnt + k2 * (tree[sum].r - tree[sum].l + 1 - tree[sum].cnt));
	tree[sum].all_max = max(tree[sum].all_max, tree[sum].max + k1_);
	tree[sum].add1 = max(tree[sum].add1_, tree[sum].add1 + k1_);
	tree[sum].max += k1, tree[sum].add1 += k1;
	tree[sum].add2_ = max(tree[sum].add2_, tree[sum].add2 + k2_);
	if(tree[sum].se != -inf) tree[sum].se += k2;
	tree[sum].add2 += k2;
}
inline void pushup(int sum){
	tree[sum].sum = tree[sum << 1].sum + tree[sum << 1 | 1].sum;
	tree[sum].all_max = max(tree[sum << 1].all_max, tree[sum << 1 | 1].all_max);
	if(tree[sum << 1].max = tree[sum << 1 | 1].max){
		tree[sum].max = tree[sum << 1].max;
		tree[sum].se = max(tree[sum << 1].se, tree[sum << 1 | 1].se);
		tree[sum].cnt = tree[sum << 1].cnt + tree[sum << 1 | 1].cnt;
	}else if(tree[sum << 1].max > tree[sum << 1 | 1].max){
		tree[sum].max = tree[sum << 1].max;
		tree[sum].se = max(tree[sum << 1].se, tree[sum << 1 | 1].max);
		tree[sum].cnt = tree[sum << 1].cnt;
	}else{
		tree[sum].max = tree[sum << 1 | 1].max;
		tree[sum].se = max(tree[sum << 1].max, tree[sum << 1 | 1].se);
		tree[sum].cnt = tree[sum << 1 | 1].cnt;
	}
}
inline void pushdown(int sum){
	int now = max(tree[sum << 1].max, tree[sum << 1 | 1].max);
	if(tree[sum << 1].max == now){
		update(tree[sum].add1, tree[sum].add1_, tree[sum].add2, tree[sum].add2_, sum << 1);
	}else update(tree[sum].add2, tree[sum].add2_, tree[sum].add2, tree[sum].add2_, sum << 1);
	if(tree[sum << 1 | 1].max == now){
		update(tree[sum].add1, tree[sum].add1_, tree[sum].add2, tree[sum].add2_, sum << 1 | 1);
	}else update(tree[sum].add2, tree[sum].add2_, tree[sum].add2, tree[sum].add2_, sum << 1 | 1);
	tree[sum].add1 = tree[sum].add1_ = tree[sum].add2 = tree[sum].add2_ = 0;
}
inline void build(int l, int r, int sum){
	tree[sum].l = l, tree[sum].r = r;
	tree[sum].add1 = tree[sum].add1_ = tree[sum].add2 = tree[sum].add2_ = 0;
 	if(l == r){
 		tree[sum].sum = tree[sum].max = tree[sum].all_max = a[l];
 		tree[sum].se = -inf, tree[sum].cnt = 1;
 		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, sum << 1);
	build(mid + 1, r, sum << 1 | 1);
	pushup(sum);
}
inline void add(int l, int r, int sum, int k){
	if(tree[sum].l > r || tree[sum].r < l) return;
	if(l <= tree[sum].l && tree[sum].r <= r){
		update(k, k, k, k, sum);
		return;
	}
	pushdown(sum);
	add(l, r, sum << 1, k);
	add(l, r, sum << 1 | 1, k);
	pushup(sum);
}
inline void modify(int l, int r, int sum, int k){
	if(tree[sum].l > r || tree[sum].r < l || k >= tree[sum].max) return;
	if(l <= tree[sum].l && tree[sum].r <= r && k > tree[sum].se){
		update(k - tree[sum].max, k - tree[sum].max, 0, 0, sum);
		return;
	}
	pushdown(sum);
	modify(l, r, sum << 1, k);
	modify(l, r, sum << 1 | 1, k);
	pushup(sum);
}
inline ll sigma(int l, int r, int sum){
	if(tree[sum].l > r || tree[sum].r < l) return 0;
	if(l <= tree[sum].l && tree[sum].r <= r) return tree[sum].sum;
	pushdown(sum);
	return sigma(l, r, sum << 1) + sigma(l, r, sum << 1 | 1);
}
inline ll query_max(int l, int r, int sum){
	if(tree[sum].l > r || tree[sum].r < l) return -inf;
	if(l <= tree[sum].l && tree[sum].r <= r) return tree[sum].max;
	pushdown(sum);
	return max(query_max(l, r, sum << 1), query_max(l, r, sum << 1 | 1));
}
inline ll query_all_max(int l, int r, int sum){
	if(tree[sum].l > r || tree[sum].r < l) return -inf;
	if(l <= tree[sum].l && tree[sum].r <= r) return tree[sum].all_max;
	pushdown(sum);
	return max(query_all_max(l, r, sum << 1), query_all_max(l, r, sum << 1 | 1));
}
signed main(){
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
    n = read(), m = read();
    for(int i = 1; i <= n; ++ i) a[i] = read();
	build(1, n, 1);
	while(m --){
		int op = read();
		if(op == 1){
			int l = read(), r = read(), k = read();
			add(l, r, 1, k);
		}else if(op == 2){
			int l = read(), r = read(), k = read();
			modify(1, r, 1, k);
		}else if(op == 3){
			int l = read(), r = read();
			write(sigma(l, r, 1)), putchar('\n');
		}else if(op == 4){
			int l = read(), r = read();
			write(query_max(l, r, 1)), putchar('\n');
		}else if(op == 5){
			int l = read(), r = read();
			write(query_all_max(l, r, 1)), putchar('\n');
		}
	} 
	return 0;
}