线段树超时？打了标记！

Kaedehara_zgb @ 2023-10-20 09:48:32

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100100;
int n, m, i, a[N], ans;
struct no {
    int sum;
};
struct lazy {
    int add;
};
struct node {
    lazy t;
    no val;
    int len;
}seg[N * 4];
no operator + (const no &l, const no &r) {
    return {l.sum + r.sum};
}
lazy operator + (const lazy &v, const lazy &t) {
    return {v.add+ t.add};
}
void update(int id) {
    seg[id].val.sum = seg[id * 2].val.sum + seg[id * 2 + 1].val.sum;
    seg[id].len = seg[id * 2].len * 2;
}
void build(int id, int l, int r) {
    if(l == r) {
        seg[id].val.sum = a[l];
        seg[id].len = 1;
        return;
    }
    int mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    update(id);
}
void setlazy(int id, lazy t) {
    seg[id].val.sum = seg[id].val.sum + t.add * seg[id].len;
    seg[id].t = seg[id].t + t;
}
void pushdown(int id) {
    if(seg[id].t.add != 0) {
        setlazy(id * 2, seg[id].t);
        setlazy(id * 2 + 1, seg[id].t);
        seg[id].t.add = 0;
    }
}
int query(int id, int l, int r, int ql, int qr) {
    if(l == qr && r == qr) return seg[id].val.sum;
    int mid = (l + r) / 2;
    pushdown(id);
    if(qr <= mid) return query(id * 2, l, mid, ql, qr);
    else if(ql > mid) return query(id * 2 + 1, mid + 1, r, ql, qr);
    else return query(id * 2, l, mid, ql, mid) + query(id * 2 + 1, mid + 1, r, mid + 1, qr);    
}
void modify(int id, int l, int r, int ql, int qr, lazy t) {
    if(l == qr && r == qr) {setlazy(id, t); return;}
    int mid = (l + r) / 2;
    pushdown(id);
    if(qr <= mid) return modify(id * 2, l, mid, ql, qr, t);
    else if(ql > mid) return modify(id * 2 + 1, mid + 1, r, ql, qr, t);
    else {
        modify(id * 2, l, mid, ql, mid, t);
        modify(id * 2 + 1, mid + 1, r, mid + 1, qr, t);
    }
    update(id);
}
signed main () {
    scanf("%lld %lld", &n, &m);
    for (i = 1; i <= n; ++i) scanf("%lld", &a[i]);
    build(1, 1, n);
    while(m--) {
        int ty;
        scanf("%lld", &ty);
        if(ty == 1) {
            int l, r, d;
            scanf("%lld %lld %lld", &l, &r, &d);
            modify(1, 1, n, l, r, (lazy){d});
        } else {
            int l, r;
            scanf("%lld %lld",&l, &r);
            ans = query(1, 1, n, l, r);
            printf("%lld\n", ans);
        }
    }
}

by Buried_Dream @ 2023-10-20 10:47:32

@Kaedehara_zgb https://www.luogu.com.cn/record/130516895

修改那些不应该 return，然后你ql 达成 qr 了，导致你都查到叶子了

by Kaedehara_zgb @ 2023-10-20 10:47:55

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100100;
int n, m, i, a[N], ans;
struct no {
    int sum;
};
struct lazy {
    int add;
};
struct node {
    lazy t;
    no val;
    int len;
}seg[N * 4];
no operator + (const no &l, const no &r) {
    return {l.sum + r.sum};
}
lazy operator + (const lazy &v, const lazy &t) {
    return {v.add+ t.add};
}
void update(int id) {
    seg[id].val.sum = seg[id * 2].val.sum + seg[id * 2 + 1].val.sum;
    seg[id].len = seg[id * 2].len * 2;
}
void build(int id, int l, int r) {
    if(l == r) {
        seg[id].val.sum = a[l];
        seg[id].len = 1;
        return;
    }
    int mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    update(id);
}
void setlazy(int id, lazy t) {
    seg[id].val.sum = seg[id].val.sum + t.add * seg[id].len;
    seg[id].t = seg[id].t + t;
}
void pushdown(int id) {
    if(seg[id].t.add != 0) {
        setlazy(id * 2, seg[id].t);
        setlazy(id * 2 + 1, seg[id].t);
        seg[id].t.add = 0;
    }
}
int query(int id, int l, int r, int ql, int qr) {
    if(l == ql && r == qr) return seg[id].val.sum;
    int mid = (l + r) / 2;
    pushdown(id);
    if(qr <= mid) return query(id * 2, l, mid, ql, qr);
    else if(ql > mid) return query(id * 2 + 1, mid + 1, r, ql, qr);
    else return query(id * 2, l, mid, ql, mid) + query(id * 2 + 1, mid + 1, r, mid + 1, qr);    
}
void modify(int id, int l, int r, int ql, int qr, lazy t) {
    if(l == ql && r == qr) {setlazy(id, t); return;}
    int mid = (l + r) / 2;
    pushdown(id);
    if(qr <= mid) modify(id * 2, l, mid, ql, qr, t);
    else if(ql > mid) modify(id * 2 + 1, mid + 1, r, ql, qr, t);
    else {
        modify(id * 2, l, mid, ql, mid, t);
        modify(id * 2 + 1, mid + 1, r, mid + 1, qr, t);
    }
    update(id);
}
signed main () {
    scanf("%lld %lld", &n, &m);
    for (i = 1; i <= n; ++i) scanf("%lld", &a[i]);
    build(1, 1, n);
    while(m--) {
        int ty;
        scanf("%lld", &ty);
        if(ty == 1) {
            int l, r, d;
            scanf("%lld %lld %lld", &l, &r, &d);
            modify(1, 1, n, l, r, (lazy){d});
        } else {
            int l, r;
            scanf("%lld %lld",&l, &r);
            ans = query(1, 1, n, l, r);
            printf("%lld\n", ans);
        }
    }
}

目前改好的代码，答案错误了，只对了3个

by Buried_Dream @ 2023-10-20 10:50:33

@Kaedehara_zgb

你的 update 写错了， 你的父亲节点的 len 应该是左右两个儿子的len的和，改过之后就AC了

by Kaedehara_zgb @ 2023-10-20 10:56:45

seg[id].len = seg[id * 2].len * 2;

改成

seg[id].len = seg[id * 2].len + seg[id * 2 + 1].len;

就对了，过了，谢谢大佬帮助。 脑子出问题了，把线段树看成了满二插

by Buried_Dream @ 2023-10-20 10:58:18

@Kaedehara_zgb 线段树就是满2叉吧，只是当 n 是奇数的时候左右儿子长度不相等

by Kaedehara_zgb @ 2023-10-20 11:02:48

@Buried_Dream ![]( 这个例子就不是呀满二叉

by Kaedehara_zgb @ 2023-10-20 11:04:20

@Kaedehara_zgb 额~

画错了，不过问题不大

by Buried_Dream @ 2023-10-20 11:07:35

@Kaedehara_zgb 哦对，是我想错了

by 小杨小小杨 @ 2023-10-20 13:34:50

@Buried_Dream ？你要不要看看你在说什么