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

P1253 扶苏的问题

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%%%%,现在懂了,感谢


|