线段树 10pts 求调

Leslie_Lau @ 2024-08-16 19:40:00

#include <iostream>
#define int long long
using namespace std;

const int N = 1e6 + 5;
const int M = 4e6 + 5;
int n, q, a[N], tree[M], lazy[M];

inline int ls (int p) {return p * 2;}
inline int rs (int p) {return p * 2 + 1;}

void build (int l, int r, int p) {
    if (l == r) {
        tree[p] = a[l];
        return ;
    }
    int mid = (l + r) / 2;
    build( l, mid, ls(p) );
    build( mid + 1, r, rs(p) );
    tree[p] = tree[ ls(p) ] + tree[ rs(p) ];
    return ;
}

void push_down (int p, int len) {
    if (lazy[p] == 0) return ;
    lazy[ ls(p) ] += lazy[p];
    lazy[ rs(p) ] += lazy[p];
    tree[ ls(p) ] += lazy[p] * (len - len / 2);
    tree[ rs(p) ] += lazy[p] * len;
    lazy[p] = 0; return ;
}

void upd (int l, int r, int d, int p, int cl, int cr) {
    int len = cr - cl + 1;
    if (cl >= l && cr <= r) {
        tree[p] += len * d;
        lazy[p] += d;
        return ;
    }
    push_down(p, len);
    int mid = (cl + cr) / 2;
    if (l <= mid) upd(l, r, d, ls(p), cl, mid);
    if (r > mid) upd(l, r, d, rs(p), mid + 1, cr);
    tree[p] = tree[ ls(p) ] + tree[ rs(p) ];
    return ;
}

int query (int l, int r, int p, int cl, int cr) {
    int len = cr - cl + 1, ans = 0;
    if (cl >= l && cr <= r) return tree[p];
    push_down(p, len);
    int mid = (cl + cr) / 2;
    if (l <= mid) ans += query(l, r, ls(p), cl, mid);
    if (r > mid) ans += query(l, r, rs(p), mid + 1, cr);
    return ans;
}

signed main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build (1, n, 1);
    int opt, x, y, z;
    while (q--) {
        cin >> opt;
        if (opt == 1) {
            cin >> x >> y >> z;
            upd(x, y, z, 1, 1, n);
        } else {
            cin >> x >> y;
            cout << query(x, y, 1, 1, n) << "\n";
        }
    }
    return 0;
}

by wh__ @ 2024-08-16 20:10:34

你 pushdown 右儿子 tag 应该要传一半段

void push_down (int p, int len) {
    if (lazy[p] == 0) return ;
    lazy[ ls(p) ] += lazy[p];
    lazy[ rs(p) ] += lazy[p];
    tree[ ls(p) ] += lazy[p] * (len - len / 2);
    tree[ rs(p) ] += lazy[p] * (len -(len - len / 2));
    lazy[p] = 0; return ;
}

by wh__ @ 2024-08-16 20:10:49

@liuhaosen

by Leslie_Lau @ 2024-08-16 20:16:27

@wh__ 谢谢 我刚改了 但还是只有30分

by wh__ @ 2024-08-16 20:22:36

@liuhaosen 自己仔细看看

#include <iostream>
#define int long long
using namespace std;

const int N = 1e6 + 5;
const int M = 4e6 + 5;
int n, q, a[N], tree[M], lazy[M];

inline int ls (int p) {return p * 2;}
inline int rs (int p) {return p * 2 + 1;}

void build (int l, int r, int p) {
    if (l == r) {
        tree[p] = a[l];
        return ;
    }
    int mid = (l + r) / 2;
    build( l, mid, ls(p) );
    build( mid + 1, r, rs(p) );
    tree[p] = tree[ ls(p) ] + tree[ rs(p) ];
    return ;
}

void push_down (int p, int len) {
    if (lazy[p] == 0) return ;
    lazy[ ls(p) ] += lazy[p];
    lazy[ rs(p) ] += lazy[p];
    tree[ ls(p) ] += lazy[p] * (len - len / 2);
    tree[ rs(p) ] += lazy[p] * (len -(len - len / 2));
    lazy[p] = 0; return ;
}

void upd (int l, int r, int d, int p, int cl, int cr) {
    int len = cr - cl + 1;
    if (cl >= l && cr <= r) {
        tree[p] += len * d;
        lazy[p] += d;
        return ;
    }
    push_down(p, len);
    int mid = (cl + cr) / 2;
    if (l <= mid) upd(l, r, d, ls(p), cl, mid);
    if (r > mid) upd(l, r, d, rs(p), mid + 1, cr);
    tree[p] = tree[ ls(p) ] + tree[ rs(p) ];
    return ;
}

int query (int l, int r, int p, int cl, int cr) {
    int len = cr - cl + 1, ans = 0;
    if (cl >= l && cr <= r) return tree[p];
    push_down(p, len);
    int mid = (cl + cr) / 2;
    if (l <= mid) ans += query(l, r, ls(p), cl, mid);
    if (r > mid) ans += query(l, r, rs(p), mid + 1, cr);
    return ans;
}

signed main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build (1, n, 1);
    int opt, x, y, z;
    while (q--) {
        cin >> opt;
        if (opt == 1) {
            cin >> x >> y >> z;
            upd(x, y, z, 1, 1, n);
        } else {
            cin >> x >> y;
            cout << query(x, y, 1, 1, n) << "\n";
        }
    }
    return 0;
}

by wh__ @ 2024-08-16 20:23:36

@liuhaosen 不是，哥们。。。这么改直接就A了啊？？？

by Leslie_Lau @ 2024-08-16 20:31:12

@wh__ 为啥 len/2 不行啊

by Leslie_Lau @ 2024-08-16 20:37:59

@wh__ 哦 我len/2没加括号 取整错了 谢谢大佬

by wh__ @ 2024-08-16 20:38:46

@liuhaosen 奇数会卡你->建议直接用 l,r 算