P1253 扶苏的问题 萌新WA+TLE(20points)求调

#include <cstdio>
#include <iostream>
#define lson rt*2, l, md
#define rson rt*2+1, md+1, r
using namespace std;

typedef long long ll;
const ll N = 1e6 + 10, INF = -114514919810;
ll n, q, a[N], xds[N*4], tag1[N*4], tag2[N*4];

void build(int rt, int l, int r){
	if (l == r){
		xds[rt] = a[l];
		return;
	}
	int md = (l + r) >> 1;
	build(lson);
	build(rson);
	xds[rt] = max(xds[rt*2], xds[rt*2+1]);
}

void cover(int rt){
	if (tag1[rt] != INF){
		xds[rt*2] = xds[rt*2+1] = tag1[rt];
		tag1[rt*2] = tag1[rt*2+1] = tag1[rt];
		tag2[rt*2] = tag2[rt*2+1] = 0;
		tag1[rt] = INF;
	}
}

void pushdown(int rt){
	cover(rt);
	if (tag2[rt]){
		xds[rt*2] += tag2[rt];
		xds[rt*2+1] += tag2[rt];
		tag2[rt*2] += tag2[rt];
		tag2[rt*2+1] += tag2[rt];
		tag2[rt] = 0;
	}
}

void update1(int rt, int l, int r, int x, int y, ll k){
	if (x <= l && r <= y){
		xds[rt] = k;
		tag1[rt] = k;
		tag2[rt] = 0;
		return;
	}
	pushdown(rt);
	int md = (l + r) >> 1;
	if (md >= x)	update1(lson, x, y, k);
	if (md < y)	update1(rson, x, y, k);
	xds[rt] = max(xds[rt*2], xds[rt*2+1]);
}

void update2(int rt, int l, int r, int x, int y, ll k){
	if (x <= l && r <= y){
		cover(rt);
		xds[rt] += k;
		tag2[rt] += k;
		return;
	}
	pushdown(rt);
	int md = (l + r) >> 1;
	if (md >= x)	update2(lson, x, y, k);
	if (md < y)	update2(rson, x, y, k);
	xds[rt] = max(xds[rt*2], xds[rt*2+1]);
}

ll query(int rt, int l, int r, int x, int y){
	if (x <= l && r <= y)
		return xds[rt];
	pushdown(rt);
	ll ans = -INF;
	int md = (l + r) >> 1;
	if (md >= x)	ans = max(ans, query(lson, x, y));
	if (md < y)	ans = max(ans, query(rson, x, y));
	return ans;
}

int main(){
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	build(1, 1, n);
	for (int i = 1; i <= n*4; i++)
		tag1[i] = INF;
	
	for (int i = 1; i <= q; i++){
		int op;
		cin >> op;
		if (op == 1){
			ll x, y, z;
			cin >> x >> y >> z;
			update1(1, 1, n, x, y, z);
		}else if (op == 2){
			ll x, y, z;
			cin >> x >> y >> z;
			update2(1, 1, n, x, y, z);
		}else{
			ll x, y;
			cin >> x >> y;
			cout << query(1, 1, n, x, y) << endl;
		}
	}
	
	return 0;
}