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

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

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

@wryyyyyyyyy 的确开到 4 倍了，但还是 wa，了。

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

@neach__joup 没事我旁边有 Himezaka_noai dalao 在调了

by Saka_Noa @ 2022-08-15 19:17:39

@wryyyyyyyyy 我谢谢你

by fajerwerki @ 2022-08-15 19:18:10

@wryyyyyyyyy 我身边的一个 dalao 如同我一样在求助QwQ

by _Luminescence_ @ 2022-08-15 19:20:01

这题的最小值好像比-INTMAX还小，当时我就是这么WA的

by fajerwerki @ 2022-08-15 19:20:50

@Day0 谢谢，50分了

by Saka_Noa @ 2022-08-15 19:25:44

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, bkn = -LONG_MAX;
int a[4000001];
struct Node {
    int l, r, val, lazy, flazy;
} tree[4000001];
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)
        fz(L, R, l, mid, lson(root), k);
    if (mid < R)
        fz(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 = -LONG_MAX;
    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 dlydly @ 2022-08-15 19:26:06

你谷平均一天可以出现10个线段树。

by _WRYYY_ @ 2022-08-15 19:26:09

兄台你赋值语句怎么还是add啊

by Saka_Noa @ 2022-08-15 19:26:26

记得开LONG_MAX
fz 调用了add 数组开小