60分线段树求助

Z_章鱼哥 @ 2023-05-03 20:26:32

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const ll inf = 1e18;

struct Node {
    int l, r;
    ll maxv, lazya, lazyx;  // lazya 维护加，lazyx 维护赋值
} tr[4 * N];
ll n, m, a[N];

void pushdown(int root) {   // 先更新值，然后下放标记
    if (tr[root].lazya) {
        tr[root].maxv += (ll)(tr[root].lazya);

        if (tr[root].l != tr[root].r) {
            tr[root << 1].lazya += (ll)(tr[root].lazya);
            tr[root << 1 | 1].lazya += (ll)(tr[root].lazya);
        }

        tr[root].lazya = 0;
    } else if (tr[root].lazyx != inf) {
        tr[root].maxv = tr[root].lazyx;

        if (tr[root].l != tr[root].r) {
            tr[root << 1].lazyx = tr[root].lazyx;
            tr[root << 1 | 1].lazyx = tr[root].lazyx;
        }

        tr[root].lazyx = inf;
    }
}

void pushup(int root) { // 先将更新儿子，再更新自己
    pushdown(root << 1);
    pushdown(root << 1 | 1);
    tr[root].maxv = max(tr[root << 1].maxv, tr[root << 1 | 1].maxv);
}

void build(int root, int l, int r) {
    tr[root].l = l, tr[root].r = r;
    tr[root].lazya = 0;
    tr[root].lazyx = inf;

    if (l == r) {
        tr[root].maxv = a[l];
    } else {
        int mid = (l + r) >> 1;
        build(root << 1, l, mid);
        build(root << 1 | 1, mid + 1, r);
        pushup(root);
    }
}

void add(int root, int l, int r, ll x) {    // 先下放标记，再操作
    pushdown(root);
    if (tr[root].l == l && tr[root].r == r) {
        tr[root].lazya += x;
    } else {
        int mid = (tr[root].l + tr[root].r) >> 1;
        if (r <= mid) {
            add(root << 1, l, r, x);
        } else if (l > mid) {
            add(root << 1 | 1, l, r, x);    // 前两种区间不变
        } else {
            add(root << 1, l, mid, x);      // 区间分成两份
            add(root << 1 | 1, mid + 1, r, x);
        }
        pushup(root);
    }
}

void modify(int root, int l, int r, ll x) {
    pushdown(root);
    if (tr[root].l == l && tr[root].r == r) {
        tr[root].lazyx = x;
    } else {
        int mid = (tr[root].l + tr[root].r) >> 1;
        if (r <= mid) {
            modify(root << 1, l, r, x);
        } else if (l > mid) {
            modify(root << 1 | 1, l, r, x);
        } else {
            modify(root << 1, l, mid, x);
            modify(root << 1 | 1, mid + 1, r, x);
        }
        pushup(root);
    }
}

ll query(int root, int l, int r) {  // 先下放标记，再询问
    pushdown(root);
    if (tr[root].l == l && tr[root].r == r) {
        return tr[root].maxv;
    } else {
        int mid = (tr[root].l + tr[root].r) >> 1;
        if (r <= mid) {
            return query(root << 1, l, r);
        } else if (l > mid) {
            return query(root << 1 | 1, l, r);
        } else {
            return max(query(root << 1, l, mid), query(root << 1 | 1, mid + 1, r));
        }
        pushup(root);
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
    }

    build(1, 1, n);
    while (m --) {
        ll op, l, r, x;
        cin >> op >> l >> r;

        if (op == 1) {
            cin >> x;
            modify(1, l, r, x);
        } else if (op == 2) {
            cin >> x;
            add(1, l, r, x);
        } else {
            cout << query(1, l, r) << "\n";
        }

        // for (int i = 1; i <= n; i ++) {
        //  cout << query(1, i, i) << " ";
        // }
        // cout << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;

    while (T --) {
        solve();
    }

    return 0;
}

by Alphaban @ 2023-05-03 20:34:53

@Z_章鱼哥 pushdown赋值和加的顺序反了

by Z_章鱼哥 @ 2023-05-03 20:39:30

@Alphaban 调换了一下顺序，也还是 60 分

by Alphaban @ 2023-05-03 20:48:42

@Z_章鱼哥

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const ll inf = 1e18;

struct Node {
    int l, r;
    ll maxv, lazya, lazyx;  // lazya 维护加，lazyx 维护赋值
} tr[4 * N];
ll n, m, a[N];

void pushdown(int root) {   // 先更新值，然后下放标记

    if (tr[root].lazyx != inf) {
        tr[root].maxv = tr[root].lazyx;

        if (tr[root].l != tr[root].r) {

            tr[root << 1].lazya = 0;//tr[root].lazyx;
            tr[root << 1 | 1].lazya = 0;//tr[root].lazyx;
            tr[root << 1].lazyx = tr[root].lazyx;
            tr[root << 1 | 1].lazyx = tr[root].lazyx;
        }

        tr[root].lazyx = inf;
    }
    if (tr[root].lazya) {
        tr[root].maxv += (ll)(tr[root].lazya);

        if (tr[root].l != tr[root].r) {
            tr[root << 1].lazya += (ll)(tr[root].lazya);
            tr[root << 1 | 1].lazya += (ll)(tr[root].lazya);
        }

        tr[root].lazya = 0;
    } 
}

void pushup(int root) { // 先将更新儿子，再更新自己
    pushdown(root << 1);
    pushdown(root << 1 | 1);
    tr[root].maxv = max(tr[root << 1].maxv, tr[root << 1 | 1].maxv);
}

void build(int root, int l, int r) {
    tr[root].l = l, tr[root].r = r;
    tr[root].lazya = 0;
    tr[root].lazyx = inf;

    if (l == r) {
        tr[root].maxv = a[l];
    } else {
        int mid = (l + r) >> 1;
        build(root << 1, l, mid);
        build(root << 1 | 1, mid + 1, r);
        pushup(root);
    }
}

void add(int root, int l, int r, ll x) {    // 先下放标记，再操作
    pushdown(root);
    if (tr[root].l == l && tr[root].r == r) {
        tr[root].lazya += x;
    } else {
        int mid = (tr[root].l + tr[root].r) >> 1;
        if (r <= mid) {
            add(root << 1, l, r, x);
        } else if (l > mid) {
            add(root << 1 | 1, l, r, x);    // 前两种区间不变
        } else {
            add(root << 1, l, mid, x);      // 区间分成两份
            add(root << 1 | 1, mid + 1, r, x);
        }
        pushup(root);
    }
}

void modify(int root, int l, int r, ll x) {
    pushdown(root);
    if (tr[root].l == l && tr[root].r == r) {
        tr[root].lazyx = x;
    } else {
        int mid = (tr[root].l + tr[root].r) >> 1;
        if (r <= mid) {
            modify(root << 1, l, r, x);
        } else if (l > mid) {
            modify(root << 1 | 1, l, r, x);
        } else {
            modify(root << 1, l, mid, x);
            modify(root << 1 | 1, mid + 1, r, x);
        }
        pushup(root);
    }
}

ll query(int root, int l, int r) {  // 先下放标记，再询问
    pushdown(root);
    if (tr[root].l == l && tr[root].r == r) {
        return tr[root].maxv;
    } else {
        int mid = (tr[root].l + tr[root].r) >> 1;
        if (r <= mid) {
            return query(root << 1, l, r);
        } else if (l > mid) {
            return query(root << 1 | 1, l, r);
        } else {
            return max(query(root << 1, l, mid), query(root << 1 | 1, mid + 1, r));
        }
        pushup(root);
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
    }

    build(1, 1, n);
    while (m --) {
        ll op, l, r, x;
        cin >> op >> l >> r;

        if (op == 1) {
            cin >> x;
            modify(1, l, r, x);
        } else if (op == 2) {
            cin >> x;
            add(1, l, r, x);
        } else {
            cout << query(1, l, r) << "\n";
        }

        // for (int i = 1; i <= n; i ++) {
        //  cout << query(1, i, i) << " ";
        // }
        // cout << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;

    while (T --) {
        solve();
    }

    return 0;
}

by Z_章鱼哥 @ 2023-05-03 20:56:55

@Alphaban 我擦，感谢大佬