RE求调

YLgiegie @ 2024-05-05 17:05:25

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 +10;
ll n , m , q;

ll a[N];
struct node{
    ll num;
    ll ls , rs;
    ll lazy;
}tr[N];
#define lson tr[rt].ls
#define rson tr[rt].rs
#define mid (lson + rson) >> 1
void build(ll rt , ll l , ll r) {
    lson = l;
    rson = r;
    if(l == r) {
        tr[rt].num = a[l];
        return;
    }
    build(rt << 1 , l , mid);
    build(rt << 1 | 1, mid + 1 , r);
    tr[rt].num = tr[rt << 1].num + tr[rt << 1 | 1].num;
}
void push(ll rt) {
    ll lazy = tr[rt].lazy;
    if(lazy) {
        tr[rt << 1].num += lazy * (tr[rt << 1].rs + tr[rt << 1].ls + 1);
        tr[rt << 1].lazy += lazy;
        tr[rt << 1 | 1].num += lazy * (tr[rt << 1 | 1].rs + tr[rt << 1 | 1].ls + 1);
        tr[rt << 1 | 1].lazy += lazy;
        tr[rt].lazy = 0;
    }
}

void update(ll rt , ll l , ll r , ll v) {
    if(l <= lson && r >= rson) {
        tr[rt].num += v * (lson + rson + 1);
        tr[rt].lazy += v;
        return;
    }
    push(rt);
    if(l <= mid) update(rt << 1 , l , r , v);
    if(r > mid) update(rt << 1 | 1 , l , r , v);
    tr[rt].num = tr[rt << 1].num + tr[rt << 1 | 1].num;
}
ll query(ll rt , ll l , ll r) {
    if(l <= lson && r >= rson) return tr[rt].num;
    push(rt);
    ll ans = 0;
    if(l <= mid) ans += query(rt << 1 , l , r);
    if(r > mid) ans += query(rt << 1 | 1 , l , r);
    return ans;
}
int main() {
    cin >> n >> m;
    for(int i = 1; i <= n ; i++) {
        cin >> a[i];
    }
    build(1 , 1 , n);
    while(m--) {
        ll op , x , y , h;
        cin >> op;
        if(op == 1) {
            cin >> x >> y >> h;
            update(1 , x , y , h);
        }
        else {
            cin >> x >> y;
            query(1 , x , y);
        }
    }
}

by Wei_Han @ 2024-05-05 17:25:06

@YLgiegie

build 里面给 mid 加个括号， 然后 update 和 push 里面区间加和应该是 (rson-lson+1)，符号写错了，还有线段树开四倍空间

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 4e5 +10;
ll n , m , q;

ll a[N];
struct node{
    ll num;
    ll ls , rs;
    ll lazy;
}tr[N<<2];
#define lson tr[rt].ls
#define rson tr[rt].rs
#define mid (lson + rson) >> 1
void build(ll rt , ll l , ll r) {
    lson = l;
    rson = r;
    if(l == r) {
        tr[rt].num = a[l];
        return;
    }
    build(rt << 1 , l , (mid));
    build(rt << 1 | 1, (mid) + 1 , r);
    tr[rt].num = tr[rt << 1].num + tr[rt << 1 | 1].num;
}
void push(ll rt) {
    ll lazy = tr[rt].lazy;
    if(lazy) {
        tr[rt << 1].num += lazy * (tr[rt << 1].rs - tr[rt << 1].ls + 1);
        tr[rt << 1].lazy += lazy;
        tr[rt << 1 | 1].num += lazy * (tr[rt << 1 | 1].rs - tr[rt << 1 | 1].ls + 1);
        tr[rt << 1 | 1].lazy += lazy;
        tr[rt].lazy = 0;
    }
}

void update(ll rt , ll l , ll r , ll v) {
    if(l <= lson && r >= rson) {
        tr[rt].num += v * (rson - lson + 1);
        tr[rt].lazy += v;
        return;
    }
    push(rt);
    if(l <= mid) update(rt << 1 , l , r , v);
    if(r > mid) update(rt << 1 | 1 , l , r , v);
    tr[rt].num = tr[rt << 1].num + tr[rt << 1 | 1].num;
}
ll query(ll rt , ll l , ll r) {
    if(l <= lson && r >= rson) return tr[rt].num;
    push(rt);
    ll ans = 0;
    if(l <= mid) ans += query(rt << 1 , l , r);
    if(r > mid) ans += query(rt << 1 | 1 , l , r);
    return ans;
}
int main() {
    cin >> n >> m;
    for(int i = 1; i <= n ; i++) {
        cin >> a[i];
    }
    build(1 , 1 , n);
    while(m--) {
        ll op , x , y , h;
        cin >> op;
        if(op == 1) {
            cin >> x >> y >> h;
            update(1 , x , y , h);
        }
        else {
            cin >> x >> y;
            cout<<query(1 , x , y)<<endl;
        }
    }
}

by YLgiegie @ 2024-05-09 15:52:18

@weihan 感谢大佬