只过 #5 #6 求条

#include <bits/stdc++.h>
using namespace std;
#define il inline
typedef long long ll;
const int N = 5e5 + 5;
int n, m, a[N];
struct node { int len, mxa, mxb, cnt, sec, tgma, tgmb, tgoa, tgob; ll sum; } t[N << 2];
#define lc p << 1
#define rc lc | 1
il void psu(int p) {
	t[p].mxa = max(t[lc].mxa, t[rc].mxa), t[p].mxb = max(t[lc].mxb, t[rc].mxb), t[p].sum = t[lc].sum + t[rc].sum;
	if (t[lc].mxa == t[rc].mxa) t[p].cnt = t[lc].cnt + t[rc].cnt, t[p].sec = max(t[lc].sec, t[rc].sec);
	else if (t[lc].mxa > t[rc].mxa) t[p].cnt = t[lc].cnt, t[p].sec = max(t[lc].sec, t[rc].mxa);
	else t[p].cnt = t[rc].cnt, t[p].sec = max(t[lc].mxa, t[rc].sec);
}
il void upd(int p, int tgma, int tgmb, int tgoa, int tgob) {
	t[p].sum += (ll)tgma * t[p].cnt + (ll)tgoa * (t[p].len - t[p].cnt);
	t[p].mxb = max(t[p].mxb, t[p].mxa + tgmb), t[p].mxa += tgma;
	if (t[p].sec ^ INT_MIN) t[p].sec += tgoa;
	t[p].tgmb = max(t[p].tgmb, t[p].tgma + tgmb), t[p].tgma += tgma;
	t[p].tgob = max(t[p].tgob, t[p].tgoa + tgob), t[p].tgoa += tgoa;
}
il void psd(int p) {
	if (!t[p].tgma && !t[p].tgmb && !t[p].tgoa && !t[p].tgob) return;
	if (t[lc].mxa == t[p].mxa) upd(lc, t[p].tgma, t[p].tgmb, t[p].tgoa, t[p].tgob);
	else upd(lc, t[p].tgoa, t[p].tgob, t[p].tgoa, t[p].tgob);
	if (t[rc].mxa == t[p].mxa) upd(rc, t[p].tgma, t[p].tgmb, t[p].tgoa, t[p].tgob);
	else upd(rc, t[p].tgoa, t[p].tgob, t[p].tgoa, t[p].tgob);
	t[p].tgma = t[p].tgmb = t[p].tgoa = t[p].tgob = 0;
}
void build(int p, int l, int r) {
	t[p].len = r - l + 1;
	if (l == r) return t[p].mxa = t[p].mxb = t[p].sum = a[l], t[p].cnt = 1, t[p].sec = INT_MIN, void();
	int mid = l + r >> 1;
	build(lc, l, mid), build(rc, mid + 1, r), psu(p);
}
void add(int p, int l, int r, int L, int R, int x) {
	if (L <= l && r <= R) {
		t[p].sum += (ll)t[p].len * x, t[p].mxb = max(t[p].mxb, t[p].mxa += x);
		if (t[p].sec ^ INT_MIN) t[p].sec += x;
		t[p].tgmb = max(t[p].tgmb, t[p].tgma += x), t[p].tgob = max(t[p].tgob, t[p].tgoa += x);
		return;
	}
	int mid = l + r >> 1; psd(p);
	if (L <= mid) add(lc, l, mid, L, R, x); if (R > mid) add(rc, mid + 1, r, L, R, x); psu(p);
}
void chkmn(int p, int l, int r, int L, int R, int x) {
	if (t[p].mxa <= x) return;
	if (L <= l && r <= R && t[p].sec < x) {
		int y = t[p].mxa - x;
		t[p].sum -= (ll)t[p].cnt * y, t[p].mxa = x;
		t[p].tgmb = max(t[p].tgmb, t[p].tgma -= y);
		return;
	}
	int mid = l + r >> 1; psd(p);
	if (L <= mid) chkmn(lc, l, mid, L, R, x); if (R > mid) chkmn(rc, mid + 1, r, L, R, x); psu(p);
}
ll qsum(int p, int l, int r, int L, int R) {
	if (L <= l && r <= R) return t[p].sum;
	int mid = l + r >> 1; ll ret = 0; psd(p);
	if (L <= mid) ret += qsum(lc, l, mid, L, R); if (R > mid) ret += qsum(rc, mid + 1, r, L, R);
	return ret;
}
int qmxa(int p, int l, int r, int L, int R) {
	if (L <= l && r <= R) return t[p].mxa;
	int mid = l + r >> 1, ret = INT_MIN; psd(p);
	if (L <= mid) ret = max(ret, qmxa(lc, l, mid, L, R)); if (R > mid) ret = max(ret, qmxa(rc, mid + 1, r, L, R));
	return ret;
}
int qmxb(int p, int l, int r, int L, int R) {
	if (L <= l && r <= R) return t[p].mxb;
	int mid = l + r >> 1, ret = INT_MIN; psd(p);
	if (L <= mid) ret = max(ret, qmxb(lc, l, mid, L, R)); if (R > mid) ret = max(ret, qmxb(rc, mid + 1, r, L, R));
	return ret;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i]; build(1, 1, n);
	while (m--) {
		int op, l, r, k; cin >> op >> l >> r;
		if (op == 1) cin >> k, add(1, 1, n, l, r, k);
		else if (op == 2) cin >> k, chkmn(1, 1, n, l, r, k);
		else if (op == 3) cout << qsum(1, 1, n, l, r) << '\n';
		else if (op == 4) cout << qmxa(1, 1, n, l, r) << '\n';
		else cout << qmxb(1, 1, n, l, r) << '\n';
	}
}