萌新刚学线段树,线段树60pts求助

P1253 扶苏的问题

shinzanmono @ 2022-09-25 09:35:30

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int sz = 1e6 + 100;
const ll inf = numeric_limits<ll>::max() + 1;
ll a[sz];
struct ST {
    ll tree[sz << 2], lazy[sz << 2], cov[sz << 2];
    bool iscov[sz << 2];
    void pushup(int p) {
        tree[p] = max(tree[p << 1], tree[p << 1 | 1]);
    }
    void pushdown(int p) {
        if (iscov[p]) {
            lazy[p << 1] = lazy[p << 1 | 1] = 0;
            tree[p << 1] = tree[p << 1 | 1] = cov[p];
            iscov[p] = false;
        }
        if (lazy[p]) {
            tree[p << 1] += lazy[p];
            lazy[p << 1] += lazy[p];
            tree[p << 1 | 1] += lazy[p];
            lazy[p << 1 | 1] += lazy[p];
            lazy[p] = 0;
        }
    }
    void build(int p, int l, int r) {
        if (l == r) return tree[p] = a[l], void();
        int mid = l + r >> 1;
        build(p << 1, l, mid);
        build(p << 1 | 1, mid + 1, r);
        pushup(p);
    }
    void add(int p, int ln, int rn, int l, int r, int val) {
        if (l > rn || r < ln) return;
        if (ln >= l && rn <= r) {
            tree[p] += val;
            lazy[p] += val;
            return;
        }
        pushdown(p);
        int mid = ln + rn >> 1;
        add(p << 1, ln, mid, l, r, val);
        add(p << 1 | 1, mid + 1, rn, l, r, val);
        pushup(p);
    }
    void assign(int p, int ln, int rn, int l, int r, int val) {
        if (l > rn || r < ln) return;
        if (ln >= l && rn <= r) {
            iscov[p] = true;
            cov[p] = val;
            tree[p] = val;
            lazy[p] = 0;
            return;
        }
        pushdown(p);
        int mid = ln + rn >> 1;
        assign(p << 1, ln, mid, l, r, val);
        assign(p << 1 | 1, mid + 1, rn, l, r, val);
        pushup(p);
    }
    ll query(int p, int ln, int rn, int l, int r) {
        if (l > rn || r < ln) return inf;
        if (ln >= l && rn <= r) return tree[p];
        ll ans = inf;
        pushdown(p);
        int mid = ln + rn >> 1;
        ans = max(ans, query(p << 1, ln, mid, l, r));
        ans = max(ans, query(p << 1 | 1, mid + 1, rn, l, r));
        return ans;
    }
} st;
int main() {
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    st.build(1, 1, n);
    while (m--) {
        int op, l, r, x;
        cin >> op >> l >> r;
        if (op == 1) cin >> x, st.assign(1, 1, n, l, r, x);
        else if (op == 2) cin >> x, st.add(1, 1, n, l, r, x);
        else cout << st.query(1, 1, n, l, r) << "\n";
    }
}

|