求助,线段树0分(求调),悬赏一个关注

P3372 【模板】线段树 1

RJSPZ @ 2022-12-01 13:19:18

#include<bits/stdc++.h>
#define maxn 100005
#define ll long long
using namespace std;
//i<<1|1=i*2+1
//加的运算优先级在C++里比位移的优先级高,所以i<<1+1=i<<(1+1)=i<<2=i*4 
#define leftson i<<1
#define rightson i<<1|1
struct node{
    int l,r,lazy;//lazy-->懒惰标记,或者延迟标记 
    ll sum;
}tree[maxn<<2];//4倍 
ll a[maxn],n,m ;
//建树 
void build(int i,int l,int r){//i=1,l=1,r=n
    tree[i].l=l;
    tree[i].r=r;
    if(l==r){//如果类似(1,1),(2,2)就算叶子结点,如果是叶子节点,就没有子节点,也就直接跳出循环。 
        tree[i].sum=a[l];
        return ;
    }
    int mid = (l+r)>>1;
    build(leftson,l,mid);//建立左子树 
    build(rightson,mid+1,r);//建立右子树 
    tree[i].sum=tree[leftson].sum+tree[rightson].sum;
    return ;
} 
void pushdown(int i){//分发任务 
    if(tree[i].lazy==0){
        tree[leftson].sum+=tree[i].lazy*(tree[leftson].r-tree[leftson].l+1);
        tree[rightson].sum+=tree[i].lazy*(tree[rightson].r-tree[rightson].l+1);
        tree[leftson].lazy+=tree[i].lazy;
        tree[rightson].lazy+=tree[i].lazy;
        tree[i].lazy=0;
    }
    return ;
}
ll ask(int i,int x,int y){
    if(tree[i].l>=x&&tree[i].r<=y){
        return tree[i].sum;
    }
    int mid=(tree[i].l+tree[i].r)/2;
    ll ans=0;
    if(mid>=x){
        ans+=ask(leftson,x,y);
    }   
    if(mid<y){
        ans+=ask(rightson,x,y);
    }
    return ans; 
} 
void update(int i,int x,int y,int d){
    if(tree[i].l>=x&&tree[i].r<=y){
        tree[i].sum+=(tree[i].r-tree[i].l+1)*d;
        tree[i].lazy+=d;
        return ;
    }
    pushdown(i);
    int mid=(tree[i].l+tree[i].r)>>1;
    if(mid>=x){
        update(leftson,x,y,d);//左孩子变化 
    }
    if(mid<y){
        update(rightson,x,y,d);//右孩子变化 
    }
    tree[i].sum=tree[leftson].sum+tree[rightson].sum;//有一个孩子改变就要更新tree[i] 
    return ;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){ 
        scanf("%d",&a[i]);
    } 
    build(1,1,n);//建立线段数组 ,根节点默认=1 
    for(int i=1;i<=m;i++){
        int op,x,y,d;
        scanf("%d%d%d",&op,&x,&y,&d);
        if(op==2){
            printf("%d\n",ask(1,x,y));
        }
        if(op==1){
            scanf("%d",&d);
            update(1,x,y,d);
        }
    }  
    return 0;
}

by Aigony @ 2022-12-01 13:31:20

@xiaogege ask里忘push_down了吧(


by RJSPZ @ 2022-12-01 13:38:56

@Aigony 写什么?


by Asimplename @ 2022-12-01 13:39:49

@xiaogege ask最开始的if后面加上Pushdown?


by SkyWave @ 2022-12-01 13:42:38

ask没下方懒标记


by RJSPZ @ 2022-12-01 13:43:37

所以怎么改呢


by Asimplename @ 2022-12-01 13:44:27



ll ask(int i,int x,int y){
    if(tree[i].l>=x&&tree[i].r<=y){
        return tree[i].sum;
    }
    pushdown(i);
    int mid=(tree[i].l+tree[i].r)/2;
    ll ans=0;
    if(mid>=x){
        ans+=ask(leftson,x,y);
    }   
    if(mid<y){
        ans+=ask(rightson,x,y);
    }
    return ans; 
} 

by Asimplename @ 2022-12-01 13:44:49

ask改成这样试试


by RJSPZ @ 2022-12-01 13:46:19

@zchqwq 不行


by SkyWave @ 2022-12-01 13:46:58

@xiaogege 不在访问内要return,不然无限递归了


by RJSPZ @ 2022-12-01 13:47:34

@SkyWave 在哪?


| 下一页