【赏关】线段树板子样例已过WA0pts带hack数据码风不离谱求调

P3372 【模板】线段树 1

Nuclear_Fish_cyq @ 2023-07-07 20:57:20

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n, m, opt, x, y, k, a[100005];
struct segment{
    ll l, r, sum, lazy;
}b[500000];
void build(ll s, ll e, ll t){
    b[t].l = s;
    b[t].r = e;
    if(s == e){
        b[t].sum = a[s];
        return;
    }
    ll p = s + ((e - s) >> 1);
    build(s, p, t * 2);
    build(p + 1, e, t * 2 + 1);
    b[t].sum = b[t * 2].sum + b[t * 2 - 1].sum;
    return;
}
ll scarch(ll t){
    if(x <= b[t].l && y >= b[t].r){
        return b[t].sum;
    }
    ll p = b[t].l + ((b[t].r - b[t].l) >> 1);
    if(b[t].lazy){
        b[t * 2].sum += b[t].lazy * (p - b[t].l + 1);
        b[t * 2 + 1].sum += b[t].lazy * (b[t].r - p);
        b[t * 2].lazy += b[t].lazy;
        b[t * 2 + 1].lazy += b[t].lazy;
    }
    b[t].lazy = 0;
    ll ans = 0;
    if(x <= p){
        ans += scarch(t * 2);
    }
    if(y > p){
        ans += scarch(t * 2 + 1);
    }
    return ans;
}
void update(ll t){
    if(x <= b[t].l && y >= b[t].r){
        b[t].sum += (b[t].r - b[t].l + 1) * k;
        b[t].lazy += k;
        return;
    }
    ll p = b[t].l + ((b[t].r - b[t].l) >> 1);
    if(b[t].lazy){
        b[t * 2].sum += b[t].lazy * (p - b[t].l + 1);
        b[t * 2 + 1].sum += b[t].lazy * (b[t].r - p);
        b[t * 2].lazy += b[t].lazy;
        b[t * 2 + 1].lazy += b[t].lazy;
    }
    b[t].lazy = 0;
    if(x <= p){
        update(t * 2);
    }
    if(y > p){
        update(t * 2 + 1);
    }
    b[t].sum = b[t * 2].sum + b[t * 2 + 1].sum;
    return;
}
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    build(1, n, 1);
    for(int i = 0; i < m; i++){
        cin >> opt;
        if(opt == 1){
            cin >> x >> y >> k;
            update(1);
        }
        else{
            cin >> x >> y;
            cout << scarch(1) << endl;
        }
    }
    return 0;
}

hack数据：

输入:

8 10
640 591 141 307 942 58 775 133 
2 1 5
2 3 8
2 3 6
2 5 8
2 4 8
1 4 8 60
2 1 6
2 5 8
1 3 7 15
1 2 6 86

正确输出：

我的输出：

我认为因为hack数据一上来就是输出操作，所以main(),build()和scarch()里面一定有至少一个错误，但与oi.wiki的代码比对多次无果。

by hjqhs @ 2023-07-07 21:06:44

你的 build 有一个地方打成 -1 了

by hjqhs @ 2023-07-07 21:07:36

@Cyq_Lyw_01 build最后pushup那里

by Nuclear_Fish_cyq @ 2023-07-07 21:07:55

@hjqhs thx!!!!!!!!!!已过，已关注，此贴结

by Nuclear_Fish_cyq @ 2023-07-07 21:08:15

wssb!!!!!

by Phrvth @ 2023-07-07 21:10:21

@Cyq_Lyw_01 第18行的 build 函数你的是

b[t].sum = b[t 2].sum + b[t 2 - 1].sum;

应为

b[t].sum = b[t 2].sum + b[t 2 + 1].sum;

建议：建议写函数，比如

ls(i) = i<<1
rs(i）= i<<1|1
push_up()
push_down()

我这里把我的代码放这里，仅供参考 ~~（个人比较喜欢用结构体封装数据结构）~~

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int MAXN = 1e5 + 7;

int n, m, a[MAXN];

struct Segt_Tree{
    struct Node{int sum, lg; }t[MAXN * 4];

    #define ls(i) (i << 1)
    #define rs(i) (i << 1 | 1)
    inline void push_up(int x) {t[x].sum = t[ls(x)].sum + t[rs(x)].sum; }

    inline void build(int cur, int l, int r){
        if (l == r) {
            t[cur].sum = a[l];
            return ;
        }
        int mid = l + r >> 1;
        build(ls(cur), l, mid); build(rs(cur), mid + 1, r);
        push_up(cur);
    }

    inline void f(int cur, int l, int r, int k){
        t[cur].sum += (r - l + 1) * k;
        t[cur].lg += k;
    }
    inline void push_down(int cur, int l, int r) {
        int mid = l + r >> 1;
        f(ls(cur), l, mid, t[cur].lg);
        f(rs(cur), mid + 1, r, t[cur].lg);
        t[cur].lg = 0;
    }

    inline void modify(int cur, int l, int r, int x, int y, int k) {
        if (x <= l && y >= r) {
            f(cur, l, r, k);
            return ;
        }
        int mid = l + r >> 1;
        push_down(cur, l, r);
        if (x <= mid) modify(ls(cur), l, mid, x, y, k);
        if (y > mid ) modify(rs(cur), mid + 1, r, x, y ,k);
        push_up(cur);
    }
    inline int query(int cur, int l, int r, int x, int y) {
        if (x <= l && y >= r) return t[cur].sum; 
        int mid = l + r >> 1, ans = 0;
        push_down(cur, l, r);
        if (x <= mid) ans += query(ls(cur), l, mid, x, y);
        if (y > mid ) ans += query(rs(cur), mid + 1, r, x, y);
        return ans;
    }
}t;

signed main () {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    t.build(1, 1, n);
    for (int i = 1, flag; i <= m; i ++) {
        cin >> flag;
        if (flag == 1) {
            int x, y, k;
            cin >> x >> y >> k;
            t.modify(1, 1, n, x, y, k);
        } else if (flag == 2) {
            int x, y;
            cin >> x >> y;
            cout << t.query(1, 1, n, x, y) << '\n';
        }
    }
    return 0;
}

by Nuclear_Fish_cyq @ 2023-07-07 21:10:57

@Phrvth 谢谢，也关注了