社区讨论
求助大神:为什么我的代码在注释处修改后便可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 条回复,欢迎继续交流。
正在加载回复...