萌新刚学OI，模板线段树求助

柠檬布丁吖 @ 2023-02-03 15:25:31

#include<bits/stdc++.h>

using namespace std;

#define ll long long
inline ll read(){
    ll ret=0,f=1;
    char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-f;
    for(;c>='0'&&c<='9';c=getchar()) ret=ret*10+c-'0';
    return ret*f;
}

const ll maxn=1e5+5;
ll n,a[maxn];
struct trees{
    ll l,r,sum,add;
}tree[maxn*4];

void pushup(ll p){
    tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
}

void pushdown(ll p){
    trees &u=tree[p],&l=tree[p<<1],&r=tree[p<<1|1];
    if(u.add){
        l.sum+=u.add*(l.r-l.l+1);
        r.sum+=u.add*(r.r-r.l+1);
        l.add+=u.add;
        r.add+=u.add;
        u.add=0;
    }
}

void build(ll p,ll l,ll r){
//  tree[p]={l,r,a[1],0};
    tree[p].l=l,tree[p].r=r,tree[p].sum=a[1],tree[p].add=0;
    if(l==r) return;
    ll m=l+r>>1;
    build(p<<1,l,m);
    build(p<<1|1,m+1,r);
    pushup(p);
}

void update(ll p,ll x,ll y,ll k){
    if(x<=tree[p].l&&tree[p].r<=y){
        tree[p].sum+=(tree[p].r-tree[p].l+1)*k;
        tree[p].add+=k;
        return;
    }

    ll m=tree[p].l+tree[p].r>>1;
    pushdown(p);
    if(x<=m) update(p<<1,x,y,k);
    if(y>m) update(p<<1|1,x,y,k);
    pushup(p);
}

ll query(ll p,ll x,ll y){
    if(x<=tree[p].l&&tree[p].r<=y){
        return tree[p].sum;
    }

    ll mid=tree[p].l+tree[p].r>>1;
    pushdown(p);
    ll sum=0;
    if(x<=mid) sum+=query(p<<1,x,y);
    if(y>mid) sum+=query(p<<1|1,x,y);
    return sum;
}

signed main(void){
    ll m;
    n=read(),m=read();

    for(ll i=1;i<=n;i++){
        a[i]=read();
    }

    build(1,1,n);

    for(ll i=1;i<=m;i++){
        int op,x,y,k;
        op=read(),x=read(),y=read();
        if(op==2) cout<<query(1,x,y);
        else cin>>k; update(1,x,y,k);
    }

    return 0;
}

by Hog_Dawa_IOI @ 2023-02-03 17:23:25

1、l+r>>1要变成(l+r)>>1，运算符优先级出错，问题出现在build函数和query函数中
2、build函数a[l]变成a[1]
3、输出忘换行
以下是完整代码：

#include<bits/stdc++.h>

using namespace std;

#define ll long long
inline ll read(){
    ll ret=0,f=1;
    char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-f;
    for(;c>='0'&&c<='9';c=getchar()) ret=ret*10+c-'0';
    return ret*f;
}

const ll maxn=1e5+5;
ll n,a[maxn];
struct trees{
    ll l,r,sum,add;
}tree[maxn*4];

void pushup(ll p){
    tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
}

void pushdown(ll p){
    trees &u=tree[p],&l=tree[p<<1],&r=tree[p<<1|1];
    if(u.add){
        l.sum+=u.add*(l.r-l.l+1);
        r.sum+=u.add*(r.r-r.l+1);
        l.add+=u.add;
        r.add+=u.add;
        u.add=0;
    }
}

void build(ll p,ll l,ll r){
    tree[p].l=l,tree[p].r=r,tree[p].sum=a[l],tree[p].add=0;
    if(l==r) return;
    ll m=(l+r)>>1;
    build(p<<1,l,m);
    build(p<<1|1,m+1,r);
    pushup(p);
}

void update(ll p,ll x,ll y,ll k){
    if(x<=tree[p].l&&tree[p].r<=y){
        tree[p].sum+=(tree[p].r-tree[p].l+1)*k;
        tree[p].add+=k;
        return;
    }

    ll m=tree[p].l+tree[p].r>>1;
    pushdown(p);
    if(x<=m) update(p<<1,x,y,k);
    if(y>m) update(p<<1|1,x,y,k);
    pushup(p);
}

ll query(ll p,ll x,ll y){
    if(x<=tree[p].l&&tree[p].r<=y){
        return tree[p].sum;
    }

    ll mid=(tree[p].l+tree[p].r)>>1;
    pushdown(p);
    ll sum=0;
    if(x<=mid) sum+=query(p<<1,x,y);
    if(y>mid) sum+=query(p<<1|1,x,y);
    return sum;
}

int main(){
    ll m;
    n=read(),m=read();

    for(ll i=1;i<=n;i++){
        a[i]=read();
    }

    build(1,1,n);

    for(ll i=1;i<=m;i++){
        int op,x,y,k;
        op=read(),x=read(),y=read();
        if(op==2) cout<<query(1,x,y)<<endl;
        else k=read(),update(1,x,y,k);
    }

    return 0;
}

by 柠檬布丁吖 @ 2023-02-03 17:50:05

@Hemingen520 谢谢！非常感谢！