如题

• Src

#include <iostream>

#define int long long

using namespace std;

const int N = 1e6 + 5;

struct Node {
	int lef, rig;
	int cvr, add, mx;
};

Node tree[N * 4];
int a[N];

void up(int id) {
    tree[id].mx = max(tree[id * 2].mx, tree[id * 2 + 1].mx);
}

void build(int id, int l, int r) {
	tree[id].lef = l; tree[id].rig = r;
	tree[id].mx = tree[id].add = 0;
	tree[id].cvr = -1145140000;
	
	if (l == r) {
		tree[id].mx = a[l];
		return;
	}
	
	int mid = (l + r) / 2;
	build(id * 2, l, mid);
	build(id * 2 + 1, mid + 1, r);
	
    up(id);
}

void cvrDown(int id) {
    if (tree[id].cvr != -1145140000) {
        tree[id * 2].add = tree[id * 2 + 1].add = 0;
        tree[id * 2].mx = tree[id * 2 + 1].mx = tree[id].cvr;
        tree[id * 2].cvr = tree[id * 2 + 1].cvr = tree[id].cvr;
        tree[id].cvr = -1145140000;
    }
}

void addDown(int id) {
    if (tree[id].add != 0) {
        tree[id * 2].mx += tree[id].add;
        tree[id * 2 + 1].mx += tree[id].add;
        tree[id * 2].add += tree[id].add;
        tree[id * 2 + 1].add += tree[id].add;
        tree[id].add = 0;
    }
}

void down(int id) {
    cvrDown(id); addDown(id);
}

void updc(int id, int l, int r, int v) {
    if (tree[id].lef > r || tree[id].rig < l) return;
    if (l <= tree[id].lef && r >= tree[id].rig) {
		tree[id].add = 0;
		tree[id].mx = v;
		tree[id].cvr = v;
		return;
	}
	down(id);
	updc(id * 2, l, r, v);
	updc(id * 2 + 1, l, r, v);
	up(id);
}

void upda(int id, int l, int r, int v) {
	if (tree[id].lef > r || tree[id].rig < l) return;
	if (l <= tree[id].lef && r >= tree[id].rig) {
	    cvrDown(id);
		tree[id].add += v;
		tree[id].mx += v;
		return;
	}
	down(id);
	upda(id * 2, l, r, v);
	upda(id * 2 + 1, l, r, v);
	up(id);
}

int query(int id, int l, int r) {
	if (tree[id].lef > r || tree[id].rig < l) return -1145140000;
	if (l <= tree[id].lef && r >= tree[id].rig) return tree[id].mx;
	down(id);
	return max(query(id * 2, l, r), query(id * 2 + 1, l, r));
}

int n, m;
int op, x, y, k;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	build(1, 1, n);
	do {
		cin >> op >> x >> y;
		if (op == 1) {
		    cin >> k;
		    updc(1, x, y, k);
		} else if (op == 2) {
			cin >> k;
			upda(1, x, y, k);
		} else {
			cout << query(1, x, y) << endl;
		}
	} while (--m);
	return 0;
}