Maple_Mourn @ 2024-11-26 20:41:50
//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;
}
by weiyiqian @ 2024-11-27 22:40:02
@Maple_Mourn 下传赋值懒标记给子节点后要把子节点的加标记清除,这个过程与父节点加标记无关
by Maple_Mourn @ 2024-11-28 18:12:33
@weiyiqian%%%%,现在懂了,感谢