线段树板子求助，悬赏关注

Shiota_Nagisa @ 2023-05-16 21:52:53

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100011];
struct tree{
    int l,r,cnt,lazy;
}t[100011];
void build(int i,int f,int s){
    t[i].l=f;
    t[i].r=s;
    if(f==s){
        t[i].cnt=a[i];
        return ;
    }
    int mid=(f+s)>>1;
    build(i*2,f,mid);
    build(i*2+1,mid+1,s);
    t[i].cnt=t[i*2].cnt+t[i*2+1].cnt;
}
void lan(int i){
    t[i*2].lazy=t[i].lazy;
    t[i*2].cnt+=(t[i*2].r-t[i*2].l+1)*t[i].lazy;
    t[i*2+1].lazy=t[i].lazy;
    t[i*2+1].cnt=(t[i*2+1].r-t[i*2+1].l+1)*t[i].lazy;
    t[i].lazy=0;
}
void add(int i,int f,int s,int v){
    if(t[i].l>s||t[i].r<f) return ;
    if(t[i].l>=f&&t[i].r<=s){
        t[i].cnt+=v*(t[i].r-t[i].l+1);
        t[i].lazy+=v;
        return ;
    }
    if(t[i].lazy>0){
        lan(i);
    }
    add(i*2,f,s,v);
    add(i*2+1,f,s,v);
    t[i].cnt=t[i*2].cnt+t[i*2+1].cnt;
}
int getsum(int i,int f,int s){
    if(t[i].l>s||t[i].r<f){
        return 0;
    }
    if(t[i].l>=f&&t[i].r<=s){
        return t[i].cnt;
    }
    if(t[i].lazy) lan(i);
    return getsum(i*2,f,s)+getsum(i*2+1,f,s);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int ask,x,y;
        cin>>ask>>x>>y;
        if(ask==2){
            cout<<getsum(1,x,y)<<endl;
        }
        else if(ask==1){
            int val;
            cin>>val;
            add(1,x,y,val);
        }
    }
    return 0;
}

by ling_luo @ 2023-05-16 22:30:47

@Manchester_Utd_FC 看见两个问题（）

2. 数组开小了啊 建议开MAXN*4

by ling_luo @ 2023-05-16 22:35:33

@Manchester_Utd_FC 还有

十年OI一场空 没开ll见祖宗

读入输出太慢 换个快读快写吧

by jokiii @ 2023-05-16 22:47:42

致命问题：建树时在叶子的赋值应为a[f]而不是a[i]。 还有传递懒标记时都应为+=

#include <iostream>
using namespace std;
int n,m,a[100011];
struct tree{
    long long l,r,cnt,lazy;
}t[500011];
void build(int i,int f,int s){
    t[i].l=f;
    t[i].r=s;
    if(f==s){
        t[i].cnt=a[f];
        return;
    }
    int mid=(f+s)>>1;
    build(i*2,f,mid);
    build(i*2+1,mid+1,s);
    t[i].cnt=t[i*2].cnt+t[i*2+1].cnt;
}
void lan(int i){
    t[i*2].lazy+=t[i].lazy;
    t[i*2].cnt+=(t[i*2].r-t[i*2].l+1)*t[i].lazy;
    t[i*2+1].lazy+=t[i].lazy;
    t[i*2+1].cnt+=(t[i*2+1].r-t[i*2+1].l+1)*t[i].lazy;
    t[i].lazy=0;
}
void add(int i,int f,int s,int v){
    if(t[i].l>s||t[i].r<f) return ;
    if(t[i].l>=f&&t[i].r<=s){
        t[i].cnt+=v*(t[i].r-t[i].l+1);
        t[i].lazy+=v;
        return ;
    }
    if(t[i].lazy>0){
        lan(i);
    }
    add(i*2,f,s,v);
    add(i*2+1,f,s,v);
    t[i].cnt=t[i*2].cnt+t[i*2+1].cnt;
}
long long getsum(int i,int f,int s){
    if(t[i].l>s||t[i].r<f){
        return 0;
    }
    if(t[i].l>=f&&t[i].r<=s){
        return t[i].cnt;
    }
    if(t[i].lazy>0) lan(i);
    return getsum(i*2,f,s)+getsum(i*2+1,f,s);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int ask,x,y;
        cin>>ask>>x>>y;
        if(ask==2){
            cout<<getsum(1,x,y)<<endl;
        }
        else if(ask==1){
            int val;
            cin>>val;
            add(1,x,y,val);
        }
    }
    return 0;
}

by Shiota_Nagisa @ 2023-05-17 21:19:19

谢谢大家，已关注