线段树全RE求调

blackmonkey @ 2023-08-25 18:41:44

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll tree[400001],lan[400001],a[100001];
int n,m;
void init(int u,int l,int r){
    if(l==r){
        tree[u]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    init(1<<u,l,mid);
    init(1<<u|1,mid+1,r);
    tree[u]=tree[u<<1]+tree[u<<1|1];    
}
void pushdown(int u,int l,int r,int mid){
    if(lan[u]==0) return;
    lan[u<<1]+=lan[u];
    tree[u<<1]+=lan[u]*(mid-l+1);
    lan[u<<1|1]+=lan[u];
    tree[u<<1|1]+=lan[u]*(r-mid);
    lan[u]=0;
}
ll query(int u,int l,int r,int ql,int qr){
    if(l==ql && r==qr) return tree[u];
    int mid=(l+r)>>1;
    pushdown(u,l,r,mid);
    if(ql<=mid && ql>mid) return query(u<<1,l,mid,ql,mid)+query(u<<1|1,mid+1,r,mid+1,qr);
    else if(qr<=mid) return query(u<<1,l,mid,ql,qr);
    else return query(u<<1|1,mid+1,r,ql,qr);
}
void modify(int u,int l,int r,int ql,int qr,ll v){
    if(l==ql && r==qr){
        tree[u]+=v*r-l+1;
        lan[u]+=v;
    }
    int mid=(l+r)>>1;
    pushdown(u,l,r,mid);
    if(ql<=mid && ql>mid){
        modify(u<<1,l,mid,ql,mid,v);
        modify(u<<1|1,mid+1,r,mid+1,qr,v);
    }
    else if(qr<=mid) modify(u<<1,l,mid,ql,qr,v);
    else modify(u<<1|1,mid+1,r,ql,qr,v);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%lld",&a[i]);
    }
    init(1,1,n);
    int id,x,y;
    long long k;
    while(m--){
        scanf("%d",&id);
        if(id==1){
            scanf("%d%d%lld",&x,&y,&k);
            modify(1,1,n,x,y,k);
        }
        else{
            scanf("%d%d",&x,&y);
            printf("%lld\n",query(1,1,n,x,y));
        }
    }
    return 0;
}

by GSRgsrgsr @ 2023-08-25 19:18:44

@blackmonkey RE是因为您modify一段区间后没return

by GSRgsrgsr @ 2023-08-25 19:19:26

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll tree[400001],lan[400001],a[100001];
int n,m;
void init(int u,int l,int r){
    if(l==r){
        tree[u]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    init(1<<u,l,mid);
    init(1<<u|1,mid+1,r);
    tree[u]=tree[u<<1]+tree[u<<1|1];    
}
void pushdown(int u,int l,int r,int mid){
    if(lan[u]==0) return;
    lan[u<<1]+=lan[u];
    tree[u<<1]+=lan[u]*(mid-l+1);
    lan[u<<1|1]+=lan[u];
    tree[u<<1|1]+=lan[u]*(r-mid);
    lan[u]=0;
}
ll query(int u,int l,int r,int ql,int qr){
    if(l>=ql && r<=qr) return tree[u];
    int mid=(l+r)>>1;
    pushdown(u,l,r,mid);
    if(ql<=mid && ql>mid) return query(u<<1,l,mid,ql,qr)+query(u<<1|1,mid+1,r,ql,qr);
    else if(qr<=mid) return query(u<<1,l,mid,ql,qr);
    else return query(u<<1|1,mid+1,r,ql,qr);
}
void modify(int u,int l,int r,int ql,int qr,ll v){
    if(l>=ql && r<=qr){
        tree[u]+=v*(r-l+1);
        lan[u]+=v;
        return;
    }
    int mid=(l+r)>>1;
    pushdown(u,l,r,mid);
    if(ql<=mid && ql>mid){
        modify(u<<1,l,mid,ql,qr,v);
        modify(u<<1|1,mid+1,r,ql,qr,v);
    }
    else if(qr<=mid) modify(u<<1,l,mid,ql,qr,v);
    else modify(u<<1|1,mid+1,r,ql,qr,v);
    tree[u]=tree[u<<1]+tree[u<<1|1];   
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%lld",&a[i]);
    }
    init(1,1,n);
    int id,x,y;
    long long k;
    while(m--){
        scanf("%d",&id);
        if(id==1){
            scanf("%d%d%lld",&x,&y,&k);
            modify(1,1,n,x,y,k);
        }
        else{
            scanf("%d%d",&x,&y);
            printf("%lld\n",query(1,1,n,x,y));
        }
    }
    return 0;
}

此外还有若干小问题，现在是WA，自己看吧

by blackmonkey @ 2023-08-25 19:20:19

谢谢大佬

by GSRgsrgsr @ 2023-08-25 19:28:39

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll tree[400001],lan[400001],a[100001];
int n,m;
void init(int u,int l,int r){
    if(l==r){
        tree[u]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    init(u<<1,l,mid);
    init(u<<1|1,mid+1,r);
    tree[u]=tree[u<<1]+tree[u<<1|1];    
}
void pushdown(int u,int l,int r,int mid){
    if(lan[u]==0) return;
    lan[u<<1]+=lan[u];
    tree[u<<1]+=lan[u]*(mid-l+1);
    lan[u<<1|1]+=lan[u];
    tree[u<<1|1]+=lan[u]*(r-mid);
    lan[u]=0;
}
ll query(int u,int l,int r,int ql,int qr){
    if(l>=ql && r<=qr) return tree[u];
    int mid=(l+r)>>1;
    pushdown(u,l,r,mid);
    if(ql<=mid && qr>mid) return query(u<<1,l,mid,ql,qr)+query(u<<1|1,mid+1,r,ql,qr);
    else if(qr<=mid) return query(u<<1,l,mid,ql,qr);
    else return query(u<<1|1,mid+1,r,ql,qr);
}
void modify(int u,int l,int r,int ql,int qr,ll v){
    if(l>=ql && r<=qr){
        tree[u]+=v*(r-l+1);
        lan[u]+=v;
        return;
    }
    int mid=(l+r)>>1;
    pushdown(u,l,r,mid);
    if(ql<=mid && qr>mid){
        modify(u<<1,l,mid,ql,qr,v);
        modify(u<<1|1,mid+1,r,ql,qr,v);
    }
    else if(qr<=mid) modify(u<<1,l,mid,ql,qr,v);
    else modify(u<<1|1,mid+1,r,ql,qr,v);
    tree[u]=tree[u<<1]+tree[u<<1|1];   
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%lld",&a[i]);
    }
    init(1,1,n);
    int id,x,y;
    long long k;
    while(m--){
        scanf("%d",&id);
        if(id==1){
            scanf("%d%d%lld",&x,&y,&k);
            modify(1,1,n,x,y,k);
        }
        else{
            scanf("%d%d",&x,&y);
            printf("%lld\n",query(1,1,n,x,y));
        }
    }
    return 0;
}

又改了好几处。。。现在过了，您自己对着找不同吧

by blackmonkey @ 2023-08-25 19:38:24

okok