题目传送门

提交记录

#include <iostream>
#include <iostream>
#include <cstdio>
#define lc (x<<1)
#define rc (x<<1)|1
#define int long long

using namespace std;

const int N = 1e6 + 1, Inf = 1000000000000000000ll;

int n, m;
int a[N];

struct tree {
	int l, r;
	int val;
	int lazy_add;
	int lazy_set;
} t[N << 2];

void pushup(int x) {
	t[x].val = max(t[lc].val, t[rc].val);
	return;
}

void maketag(int x, int k, int type) {
	if (type) {
		t[x].val += k;
		if (t[x].lazy_set != Inf)
			t[x].lazy_set += k;
		else
			t[x].lazy_add += k;
	} else {
		t[x].val = t[x].lazy_set = k;
		t[x].lazy_add = 0;
	}
	return;
}

void pushdown(int x) {
	if (t[x].lazy_set != Inf) {
		maketag(lc, t[x].lazy_set, 0);
		maketag(rc, t[x].lazy_set, 0);
		t[x].lazy_set = Inf;
	} else if (t[x].lazy_add) {
		maketag(lc, t[x].lazy_add, 1);
		maketag(rc, t[x].lazy_add, 1);
		t[x].lazy_add = 0;
	}
	return;
}

void build(int l, int r, int x) {
	t[x].l = l, t[x].r = r, t[x].lazy_set = Inf;
	if (l == r) {
		t[x].val = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, lc), build(mid + 1, r, rc);
	pushup(x);
	return;
}

void update(int l, int r, int k, int type, int x) {
	if (t[x].l > r || t[x].r < l)
		return;
	if (l <= t[x].l && t[x].r <= r) {
		maketag(x, k, type);
		return;
	}
	pushdown(x);
	update(l, r, k, type, lc), update(l, r, k, type, rc);
	pushup(x);
	return;
}

int ask(int l, int r, int x) {
	if (t[x].l > r || t[x].r < l)
		return 0;
	if (l <= t[x].l && t[x].r <= r)
		return t[x].val;
	pushdown(x);
	int maxn = max(ask(l, r, lc), ask(l, r, rc));
	pushup(x);
	return maxn;
}

signed main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++ )
		scanf("%d", a + i);
	build(1, n, 1);
	for (int i = 1; i <= m; i ++ ) {
		int op;
		scanf("%d", &op);
		if (op == 1 || op == 2) {
			int l, r, x;
			scanf("%d%d%d", &l, &r, &x);
			update(l, r, x, (op - 1), 1);
		} else if (op == 3) {
			int l, r;
			scanf("%d%d", &l, &r);
			printf("%d\n", ask(l, r, 1));
		}
	}
	return 0;
}