社区讨论

求助大神:为什么我的代码在注释处修改后便可AC,不修改则会WA 60?

P1253扶苏的问题参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@m3yg5khv
此快照首次捕获于
2024/11/26 20:42
去年
此快照最后确认于
2025/11/04 13:52
4 个月前
查看原帖
CPP
//WA 60 代码如下
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll MX = 1e6 + 5;
const ll MN = -1e15 - 1;

ll n, q, a[MX], w[4 * MX], lz1[4 * MX], lz2[4 * MX];

ll ls(ll p) {
	return p << 1;
}

int rs(ll p) {
	return p << 1 | 1;
}

void down1(ll p, ll pl, ll pr) {
	w[ls(p)] = w[rs(p)] = lz1[p];
	lz1[ls(p)] = lz1[rs(p)] = lz1[p];
	lz1[p] = MN;
	lz2[p] = lz2[ls(p)] = lz2[rs(p)] = 0;//此行修改为  lz2[ls(p)] = lz2[rs(p)] = 0; 便可 AC 
}

void down2(ll p, ll pl, ll pr) {
	w[ls(p)] += lz2[p];
	w[rs(p)] += lz2[p];
	lz2[ls(p)] += lz2[p];
	lz2[rs(p)] += lz2[p];
	lz2[p] = 0;
}

void change(ll p, ll pl, ll pr, ll l, ll r, ll x) {
	if (pl > r || pr < l) return ;
	if (pl >= l && pr <= r) {
		w[p] = x;
		lz1[p] = x;
		lz2[p] = 0;
		return ;
	}
	if (lz1[p] != MN) down1(p, pl, pr);
	if (lz2[p]) down2(p, pl, pr);
	ll mid = (pl + pr) >> 1;
	if (mid >= l) change(ls(p), pl, mid, l, r, x);
	if (mid + 1 <= r) change(rs(p), mid + 1, pr, l, r, x);
	w[p] = max(w[ls(p)], w[rs(p)]);
}

void add(ll p, ll pl, ll pr, ll l, ll r, ll x) {
	if (pl > r || pr < l) return ;
	if (pl >= l && pr <= r) {
		w[p] += x;
		lz2[p] += x;
		return ;
	}
	if (lz1[p] != MN) down1(p, pl, pr);
	if (lz2[p]) down2(p, pl, pr);
	ll mid = (pl + pr) >> 1;
	if (mid >= l) add(ls(p), pl, mid, l, r, x);
	if (mid + 1 <= r) add(rs(p), mid + 1, pr, l, r, x);
	w[p] = max(w[ls(p)], w[rs(p)]);
}

ll ask(ll p, ll pl, ll pr, ll l, ll r) {
	ll ans = MN;
	if (pl >= l && pr <= r) {
		return w[p];
	}
	if (lz1[p] != MN) down1(p, pl, pr);
	if (lz2[p]) down2(p, pl, pr);
	ll mid = (pl + pr) >> 1;
	if (mid >= l) ans = max(ans, ask(ls(p), pl, mid, l, r));
	if (mid + 1 <= r) ans = max(ans, ask(rs(p), mid+1, pr, l, r));
	return ans;
}

void build(ll p, ll l, ll r) {
	if (l == r) {
		w[p] = a[l];
		return ;
	}
	ll mid = (l + r) >> 1;
	build(ls(p), l, mid);
	build(rs(p), mid + 1, r);
	w[p] = max(w[ls(p)], w[rs(p)]);
}

int main() {
	cin >> n >> q;
	for (ll i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
	}
	
	for(ll i = 1; i <= 4 * n; i++) {
		w[i] = MN;
		lz1[i] = MN;
	}
	build(1, 1, n);
	
	while(q--) {
		ll op, x, y, k;
		scanf("%lld%lld%lld", &op, &x, &y);
		if (op == 1) {
			scanf("%lld", &k);
			change(1, 1, n, x, y, k);
		} else if (op == 2) {
			scanf("%lld", &k);
			add(1, 1, n, x, y, k);
		} else {
			printf("%lld\n", ask(1, 1, n, x, y));
		}
	}
	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...