线段树50pts WA最后5个点求调

P1253 扶苏的问题

senak @ 2024-05-04 00:32:29

Orz

#include<iostream>
#define lc p<<1
#define rc p<<1|1
#define int long long 
using namespace std;
const int N = 1E6 + 7;
const int M = 1e18;
int a[N];
struct Node {
    int l, r, mx, add, alt;
}t[N << 2];
void pushup(int p) {
    t[p].mx = max(t[lc].mx, t[rc].mx);
}
void pushdown(int p) {
    if (t[p].alt != M) {
        t[lc].mx = t[p].mx;
        t[rc].mx = t[p].mx;
        t[lc].alt = t[rc].alt = t[p].alt;
        t[lc].add = t[rc].add = 0;
        t[p].alt = M;
    }
    if (t[p].add) {
        t[lc].mx = t[lc].mx + t[p].add;
        t[rc].mx = t[rc].mx + t[p].add;
        t[lc].add = (t[p].add + t[lc].add);
        t[rc].add = (t[p].add + t[rc].add);
        t[p].add = 0;

    }
}
void update_alt(int p, int l, int r, int k) {
    if (l > t[p].r || r < t[p].l) return;
    if (l <= t[p].l && t[p].r <= r) {
        t[p].mx = k;
        t[p].alt = k; t[p].add = 0;
        return;
    }
    pushdown(p);
    update_alt(lc, l, r, k);
    update_alt(rc, l, r, k);
    pushup(p);
}
void update_add(int p, int l, int r, int k) {
    if (l > t[p].r || r < t[p].l) return;
    if (l <= t[p].l && t[p].r <= r) {
        t[p].mx += k;
        t[p].add = t[p].add + k;
        return;
    }
    pushdown(p);
    update_add(lc, l, r, k);
    update_add(rc, l, r, k);
    pushup(p);
}
void build(int p, int l, int r) {
    t[p] = { l,r,a[l],0,M };
    if (l == r) return;
    int mid = l + r >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
    pushup(p);
}
int query(int p, int l, int r) {
    if (l > t[p].r || r < t[p].l) return 0;
    if (l <= t[p].l && t[p].r <= r) {
        return t[p].mx;
    }
    pushdown(p);
    int ls = query(lc, l, r);
    int rs = query(rc, l, r);
    return max(ls, rs);
}
void solve() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++)cin >> a[i];
    build(1, 1, n);
    for (int i = 1; i <= m; i++) {
        int op; cin >> op;
        if (op == 1) {
            int l, r, x; cin >> l >> r >> x;
            update_alt(1, l, r, x);
        }
        else if (op == 2) {
            int l, r, x; cin >> l >> r >> x;
            update_add(1, l, r, x);
        }
        else if (op == 3) {
            int l, r; cin >> l >> r;
            cout << query(1, l, r) << endl;
        }
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

by cokle @ 2024-05-04 02:19:27

@senak

        pushdown:
    t[lc].mx = t[p].mx; => t[lc].mx = t[p].alt;
    t[rc].mx = t[p].mx; => t[rc].mx = t[p].alt;

        query:
        if (l > t[p].r || r < t[p].l) return 0; => if (l > t[p].r || r < t[p].l) return -M;

by senak @ 2024-05-04 10:09:22

@cokle 非常感谢!


|