rt.赏一关

# include <bits/stdc++.h>
# define ll long long
# define N 1000010
# define inf 1000000000000000000ll

using namespace std;

ll a[N], w[N * 4], lzy1[N * 4], lzy2[N * 4];
ll k;
int n, m, op, x, y;

// 建树
void pushup (int u) {
	w[u] = max (w[u * 2], w[u * 2 + 1]);
}

void build (int u, int L, int R) {
	if (L == R) {
		w[u] = a[L];
		lzy2[u] = inf;
		return ;
	}
	int mid = (L + R) / 2;
	build (u * 2, L, mid);
	build (u * 2 + 1, mid + 1, R);
	pushup (u);
}

// 单点查询
ll query1 (int u, int L, int R, int p) {
	if (L == R) return w[u];
	else {
		int mid = (L + R) / 2;
		if (mid >= p) return query1 (u * 2, L, mid, p);
		else return query1 (u * 2 + 1, mid + 1, R, p);
	}
}

// 单点修改
void update1 (int u, int L, int R, int p, ll x) {
	if (L == R) w[u] = x;
	else {
		int mid = (L + R) / 2;
		if (mid >= p) update1 (u * 2, L, mid, p, x);
		else update1 (u * 2 + 1, mid + 1, R, p, x);
		pushup (u);
	}
}

// 区间查询
bool InRange (int L, int R, int l, int r) {
	return (l <= L) && (R <= r);
}

bool OutofRange (int L, int R, int l, int r) {
	return (L > r) || (R < l);
}

ll query1 (int u, int L, int R, int l, int r) {
	if (InRange (L, R, l, r)) return w[u];
	else if (! OutofRange (L, R, l, r)) {
		int mid = (L + R) / 2;
		return query1 (u * 2, L, mid, l, r) + query1 (u * 2 + 1, mid + 1, R, l, r);
	} else return 0;
}

// 区间修改
void maketag (int u, ll x, int type) {
	if (type == 1) {
		lzy1[u] = 0;
		lzy2[u] = x;
		w[u] = x;
	} else {
		if (lzy2[u] == inf) lzy1[u] += x;
		else lzy2[u] += x;
		w[u] += x;
	}
}

void pushdown (int u, int L, int R) {
	if (lzy2[u] == inf) {
		maketag (u * 2, lzy1[u], 2);
		maketag (u * 2 + 1, lzy1[u], 2);
		lzy1[u] = 0;
	} else {
		maketag (u * 2, lzy2[u], 1);
		maketag (u * 2 + 1, lzy2[u], 1);
		lzy2[u] = inf;
	}
}

ll query (int u, int L, int R, int l, int r) {
	if (InRange (L, R, l, r)) return w[u];
	pushdown (u, L, R);
	int mid = (L + R) / 2;
	ll ans = -inf;
	if (l <= mid) ans = max (ans, query (u * 2, L, mid, l, r));
	if (r > mid) ans = max (ans, query (u * 2 + 1, mid + 1, R, l, r));
	return ans;
}

void update (int u, int L, int R, int l, int r, ll x, int type) {
	pushdown (u, L, R);
	if (InRange (L, R, l, r)) {
		maketag (u, x, type);
		return ;
	}
	int mid = (L + R) / 2;
	if (l <= mid) update (u * 2, L, mid, l, r, x, type);
	if (r > mid) update (u * 2 + 1, mid + 1, R, l, r, x, type);
	pushup (u);
}

int main () {

	scanf ("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++) scanf ("%lld", &a[i]);
	build (1, 1, n);
	for (int i = 1; i <= m; i ++) {
		scanf ("%d", &op);
		if (op == 1) {
			scanf ("%d%d%lld", &x, &y, &k);
			update (1, 1, n, x, y, k, 1);
		} else if (op == 2) {
			scanf ("%d%d%lld", &x, &y, &k);
			update (1, 1, n, x, y, k, 2);
		} else if (op == 3) {
			scanf ("%d%d", &x, &y);
			printf ("%lld\n", query (1, 1, n, x, y));
		}
	}

	return 0;

}