萌新秣子刚学OI，线段树裸题40分求调

fajerwerki @ 2022-08-15 19:05:43

by fajerwerki @ 2022-08-15 19:06:00

#include <iostream>
#define int long long
using namespace std;
int n, m, bkn = 11451419198107;
int a[1000001];
struct Node {
    int l, r, val, lazy, flazy;
} tree[1000001];
inline int lson(int root) {
    return root << 1;
}
inline int rson(int root) {
    return root << 1 | 1;
}
inline void Upload(int root) {
    tree[root].val = max(tree[rson(root)].val, tree[lson(root)].val);
}
inline void Build(int l, int r, int root) {
    tree[root].l = l, tree[root].r = r;
    tree[root].lazy = 0;tree[root].flazy = bkn;
    if (l == r) {
        tree[root].val = a[l];
        return ;
    }
    int mid = l + r >> 1;
    Build(l, mid, lson(root));
    Build(mid + 1, r, rson(root));
    Upload(root);
}
inline void tip1(int l, int r, int root, int val) {
    tree[root].val += val;
    if(tree[root].flazy != bkn) {
        tree[root].flazy += val;
    } else {
        tree[root].lazy += val;
    }
}
inline void tip2(int l, int r, int root, int val) {
    tree[root].flazy = val;
    tree[root].val = val;
    tree[root].lazy = 0;
}
inline void download1(int l, int r, int root) {
    if(tree[root].lazy != 0) {
        int mid = l + r >> 1;
        tip1(l, mid, lson(root), tree[root].lazy);
        tip1(mid + 1, r, rson(root), tree[root].lazy);
        tree[root].lazy = 0;
    }
}
inline void download2(int l, int r, int root) {
    if(tree[root].flazy != bkn) {
        int mid = l + r >> 1;
        tip2(l, mid, lson(root), tree[root].flazy);
        tip2(mid + 1, r, rson(root), tree[root].flazy);
        tree[root].flazy = bkn;
    }
}
inline void add(int L, int R, int l, int r, int root, int k) {
    if (L <= l && r <= R) {
        tip1(l, r, root, k);
        return ;
    }
    download1(l, r, root);
    download2(l, r, root);
    int mid = l + r >> 1;
    if (L <= mid)
        add(L, R, l, mid, lson(root), k);
    if (mid < R)
        add(L, R, mid + 1, r, rson(root), k);
    Upload(root);
}
inline void fz(int L, int R, int l, int r, int root, int k) {
    if (L <= l && r <= R) {
        tip2(l, r, root, k);
        return ;
    }
    download1(l, r, root);
    download2(l, r, root);
    int mid = l + r >> 1;
    if (L <= mid)
        add(L, R, l, mid, lson(root), k);
    if (mid < R)
        add(L, R, mid + 1, r, rson(root), k);
    Upload(root);
}
inline int Query(int L, int R, int l, int r, int root) {
    if (L <= l && r <= R)
        return tree[root].val;
    download1(l, r, root);
    download2(l, r, root);
    int mid = l + r >> 1, ans = -2147483647;
    if (L <= mid)
        ans = max(Query(L, R, l, mid, lson(root)), ans);
    if (mid < R)
        ans = max(ans, Query(L, R, mid + 1, r, rson(root)));
    return ans;
}
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    Build(1, n, 1);
    for (int i = 1; i <= m; i++) {
        int num;
        cin >> num;
        if (num == 2) {
            int x, y, k;
            cin >> x >> y >> k;
            add(x, y, 1, n, 1, k);
        } else {
            if (num == 3) {
                int x, y;
                cin >> x >> y;
                cout << Query(x, y, 1, n, 1) << '\n';
            } else {
                int x, y, k;
                cin >> x >> y >> k;
                fz(x, y, 1, n, 1, k);
            }
        }
    }
    return 0;
}

by Saka_Noa @ 2022-08-15 19:09:23

不是装秣子吧（逃

by 大眼仔Happy @ 2022-08-15 19:10:13

最近都是这些，不是抹子、袜子就是秣子，笑死

by _WRYYY_ @ 2022-08-15 19:10:58

求助阔以

但不要装秣子

肉眼可见错误有一个，数组开小了

by fajerwerki @ 2022-08-15 19:12:15

@wryyyyyyyyy 谢谢，没看到题目 1e6，现在还是 40 分

by fajerwerki @ 2022-08-15 19:12:44

@xs_siqi

《#define int long long》

by _WRYYY_ @ 2022-08-15 19:13:08

看错了（逃

by xs_siqi @ 2022-08-15 19:13:57

@neach__joup 我之前没看到。（悲

by fajerwerki @ 2022-08-15 19:14:15

QwQ

by _WRYYY_ @ 2022-08-15 19:14:49

@wryyyyyyyyy 错上加错，还是应该开到4倍