第一次打线段树不对心态爆炸求调QAQ

godess @ 2024-12-11 16:46:30

#include <bits/stdc++.h>
#define fo(x,a,b) for(register int (x)=(a);(x)<=(b);++(x))
#define lc p<<1
#define rc p<<1|1
using namespace std;
const int M=1e5+3;
struct node{
    int l,r,v,add;
}t[4*M];
int a[M],q,x,y,k;
void build(int l,int r,int p){
    t[p]={l,r,a[l]};
    if(l==r) return;
    int m=l+r>>1;
    build(l,m,lc);
    build(m+1,r,rc);
    t[p].v=t[lc].v+t[rc].v;
}
int query(int l,int r,int p){
    if(t[p].l>=l&&t[p].r<=r)return t[p].v;
    int ans=0;
    int m=t[p].l+t[p].r>>1;
    if(m>=l) ans+=query(l,r,lc);
    if(m<r) ans+=query(l,r,rc);
    return ans;
} 
void pushdown(int p){
    if(t[p].add){
        t[lc].v+=t[p].add*(t[lc].r-t[lc].l+1);
        t[rc].v+=t[p].add*(t[rc].r-t[rc].l+1);
        t[lc].add+=t[p].add;
        t[rc].add+=t[p].add;
        t[p].add=0;
    }
}
void update(int l,int r,int p,int k){
    if(t[p].l>=l&&t[p].r<=r){
        t[p].v+=k*(t[p].r-t[p].l+1);
        t[p].add+=k;
        return;
    }
    int m=t[p].l+t[p].r>>1;
    pushdown(p);
    if(m>=l) update(l,r,lc,k);
    if(m<r) update(l,r,rc,k);
    t[p].v=t[lc].v+t[rc].v;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    fo(i,1,n)cin>>a[i];
    build(1,n,1);
    fo(i,1,m){
        cin>>q;
        if(q==1){
            cin>>x>>y>>k;
            update(x,y,1,k);
        }else{
            cin>>x>>y;
            cout<<query(x,y,1)<<"\n";
        }
    }
    return 0;
}

by _xguagua_Firefly_ @ 2024-12-11 16:55:05

@godess

1. 在 query 的时候也要 pushdown
2. 不开 long long 见祖宗

#include <bits/stdc++.h>
#define int long long
#define fo(x,a,b) for(register int (x)=(a);(x)<=(b);++(x))
#define lc p<<1
#define rc p<<1|1
using namespace std;
const int M=1e5+3;
struct node{
    int l,r,v,add;
}t[4*M];
int a[M],q,x,y,k;
void build(int l,int r,int p){
    t[p]={l,r,a[l]};
    if(l==r) return;
    int m=l+r>>1;
    build(l,m,lc);
    build(m+1,r,rc);
    t[p].v=t[lc].v+t[rc].v;
}
void pushdown(int p){
    if(t[p].add){
        t[lc].v+=t[p].add*(t[lc].r-t[lc].l+1);
        t[rc].v+=t[p].add*(t[rc].r-t[rc].l+1);
        t[lc].add+=t[p].add;
        t[rc].add+=t[p].add;
        t[p].add=0;
    }
}
int query(int l,int r,int p){
    if(t[p].l>=l&&t[p].r<=r)return t[p].v;
    int ans=0;
    pushdown(p);
    int m=t[p].l+t[p].r>>1;
    if(m>=l) ans+=query(l,r,lc);
    if(m<r) ans+=query(l,r,rc);
    return ans;
} 
void update(int l,int r,int p,int k){
    if(t[p].l>=l&&t[p].r<=r){
        t[p].v+=k*(t[p].r-t[p].l+1);
        t[p].add+=k;
        return;
    }
    int m=t[p].l+t[p].r>>1;
    pushdown(p);
    if(m>=l) update(l,r,lc,k);
    if(m<r) update(l,r,rc,k);
    t[p].v=t[lc].v+t[rc].v;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    fo(i,1,n)cin>>a[i];
    build(1,n,1);
    fo(i,1,m){
        cin>>q;
        if(q==1){
            cin>>x>>y>>k;
            update(x,y,1,k);
        }else{
            cin>>x>>y;
            cout<<query(x,y,1)<<"\n";
        }
    }
    return 0;
}

by _xguagua_Firefly_ @ 2024-12-11 16:55:23

@godess

壶关一下？

by godess @ 2024-12-11 16:58:55

@_xguaguaFirefly豪德豪德Thanks♪(･ω･)ﾉ