萌新妹子线段树0pts求调

Lovely_Cheese @ 2024-02-04 21:04:05

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,a[114514];
struct node{
    int l,r,val;
}tree[114514*4];
int lazy[114514*4];
void build(int p,int l,int r){
    tree[p].l=l; tree[p].r=r;
    tree[p].val=a[l]; lazy[p]=0;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1+1,mid+1,r);
    tree[p].val=tree[p<<1].val+tree[p<<1+1].val;
    return ;
}
void pushdown(int p){
    if(lazy[p]){
        tree[p<<1].val+=lazy[p]*(tree[p<<1].r-tree[p].l+1);
        tree[p<<1+1].val+=lazy[p]*(tree[p<<1+1].r-tree[p<<1+1].l+1);
        lazy[p<<1]+=lazy[p]; lazy[p<<1+1]+=lazy[p]; lazy[p]=0;
    }
    return ;
}
void update(int p,int l,int r,int val){
    if(l<=tree[p].l&&tree[p].r<=r){
        tree[p].val+=(tree[p].r-tree[p].l+1)*val;
        lazy[p]+=val;
        return ;
    }
    pushdown(p);
    int mid=(tree[p].l+tree[p].r)>>1;
    if(l<=mid) update(p<<1,l,r,val);
    if(r>mid) update(p<<1+1,l,r,val);
    tree[p].val=tree[p<<1].val+tree[p<<1+1].val;
    return ; 
}
int query(int p,int l,int r){
    if(l<=tree[p].l&&tree[p].r<=r) return tree[p].val;
    pushdown(p);
    int sum=0,mid=(tree[p].l+tree[p].r)>>1;
    if(l<=mid) sum+=query(p<<1,l,r);
    if(r>mid) sum+=query(p<<1+1,l,r);
    return sum;
}
signed main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(q--){
        int op;
        cin>>op;
        if(op==1){
            int l,r,x;
            cin>>l>>r>>x;
            update(1,l,r,x);
        }
        else if(op==2){
            int l,r;
            cin>>l>>r;
            cout<<query(1,l,r)<<endl;
        }
    }
    return 0;
}

by ICU152_QWQ_IS8 @ 2024-02-04 21:10:24

@Lovely_Cheese

改的地方打了注释，但RE4~10,WA1~3

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,a[114514];
struct node{
    int l,r,val;
}tree[114514*4];
int lazy[114514*4];
void build(int p,int l,int r){
    tree[p].l=l; tree[p].r=r;
    tree[p].val=a[l]; lazy[p]=0;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1+1,mid+1,r);
    tree[p].val=tree[p<<1].val+tree[p<<1+1].val;
    return ;
}
void pushdown(int p){
    if(lazy[p]){
        tree[p<<1].val+=lazy[p]*(tree[p<<1].r-tree[p].l+1);
        tree[p<<1+1].val+=lazy[p]*(tree[p<<1+1].r-tree[p<<1+1].l+1);
        lazy[p<<1]+=lazy[p]; lazy[p<<1+1]+=lazy[p]; lazy[p]=0;
    }
    return ;
}
void update(int p,int l,int r,int val){
    if(l<=tree[p].l&&tree[p].r<=r){
        tree[p].val+=(tree[p].r-tree[p].l+1)*val;
        lazy[p]+=val;
        return ;
    }
    pushdown(p);
    int mid=(tree[p].l+tree[p].r)>>1;
    if(l<=mid) update(p<<1,l,mid,val);//-----------------
    if(r>mid) update(p<<1+1,mid+1,r,val);//----------------
    tree[p].val=tree[p<<1].val+tree[p<<1+1].val;
    return ; 
}
int query(int p,int l,int r){
    if(l<=tree[p].l&&tree[p].r<=r) return tree[p].val;
    pushdown(p);
    int sum=0,mid=(tree[p].l+tree[p].r)>>1;
    if(l<=mid) sum+=query(p<<1,l,mid);//--------------
    if(r>mid) sum+=query(p<<1+1,mid+1,r);//-------------
    return sum;
}
signed main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(q--){
        int op;
        cin>>op;
        if(op==1){
            int l,r,x;
            cin>>l>>r>>x;
            update(1,l,r,x);
        }
        else if(op==2){
            int l,r;
            cin>>l>>r;
            cout<<query(1,l,r)<<endl;
        }
    }
    return 0;
}

by WilliamFranklin @ 2024-02-04 21:10:27

@Lovely_Cheese 你将所有的 p<<1+1 改为 p<<1|1 试试

by ICU152_QWQ_IS8 @ 2024-02-04 21:12:40

@Lovely_Cheese 你pushdown给val赋值的地方也有问题

by WilliamFranklin @ 2024-02-04 21:12:56

妹子怎么也这么臭呢？

by Lovely_Cheese @ 2024-02-04 21:16:04

@ICU152_QWQ_IS8 @WilliamFranklin

现在变成全WA了

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,a[114514];
struct node{
    int l,r,val;
}tree[114514*4];
int lazy[114514*4];
void build(int p,int l,int r){
    tree[p].l=l; tree[p].r=r;
    tree[p].val=a[l]; lazy[p]=0;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    tree[p].val=tree[p<<1].val+tree[p<<1|1].val;
    return ;
}
void pushdown(int p){
    if(lazy[p]){
        tree[p<<1].val+=lazy[p]*(tree[p<<1].r-tree[p<<1].l+1);
        tree[p<<1|1].val+=lazy[p]*(tree[p<<1|1].r-tree[p<<1|1].l+1);
        lazy[p<<1]+=lazy[p]; lazy[p<<1|1]+=lazy[p]; lazy[p]=0;
    }
    return ;
}
void update(int p,int l,int r,int val){
    if(l<=tree[p].l&&tree[p].r<=r){
        tree[p].val+=(tree[p].r-tree[p].l+1)*val;
        lazy[p]+=val;
        return ;
    }
    pushdown(p);
    int mid=(tree[p].l+tree[p].r)>>1;
    if(l<=mid) update(p<<1,l,mid,val);
    if(r>mid) update(p<<1|1,mid+1,r,val);
    tree[p].val=tree[p<<1].val+tree[p<<1|1].val;
    return ; 
}
int query(int p,int l,int r){
    if(l<=tree[p].l&&tree[p].r<=r) return tree[p].val;
    pushdown(p);
    int sum=0,mid=(tree[p].l+tree[p].r)>>1;
    if(l<=mid) sum+=query(p<<1,l,mid);
    if(r>mid) sum+=query(p<<1|1,mid+1,r);
    return sum;
}
signed main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(q--){
        int op;
        cin>>op;
        if(op==1){
            int l,r,x;
            cin>>l>>r>>x;
            update(1,l,r,x);
        }
        else if(op==2){
            int l,r;
            cin>>l>>r;
            cout<<query(1,l,r)<<endl;
        }
    }
    return 0;
}

by Lovely_Cheese @ 2024-02-04 21:20:52

@ICU152_QWQ_IS8 草，大佬你好像把我的代码改错了。我改回去AC了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,a[114514];
struct node{
    int l,r,val;
}tree[114514*4];
int lazy[114514*4];
void build(int p,int l,int r){
    tree[p].l=l; tree[p].r=r;
    tree[p].val=a[l]; lazy[p]=0;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    tree[p].val=tree[p<<1].val+tree[p<<1|1].val;
    return ;
}
void pushdown(int p){
    if(lazy[p]){
        tree[p<<1].val+=lazy[p]*(tree[p<<1].r-tree[p<<1].l+1);
        tree[p<<1|1].val+=lazy[p]*(tree[p<<1|1].r-tree[p<<1|1].l+1);
        lazy[p<<1]+=lazy[p]; lazy[p<<1|1]+=lazy[p]; lazy[p]=0;
    }
    return ;
}
void update(int p,int l,int r,int val){
    if(l<=tree[p].l&&tree[p].r<=r){
        tree[p].val+=(tree[p].r-tree[p].l+1)*val;
        lazy[p]+=val;
        return ;
    }
    pushdown(p);
    int mid=(tree[p].l+tree[p].r)>>1;
    if(l<=mid) update(p<<1,l,r,val);
    if(r>mid) update(p<<1|1,l,r,val);
    tree[p].val=tree[p<<1].val+tree[p<<1|1].val;
    return ; 
}
int query(int p,int l,int r){
    if(l<=tree[p].l&&tree[p].r<=r) return tree[p].val;
    pushdown(p);
    int sum=0,mid=(tree[p].l+tree[p].r)>>1;
    if(l<=mid) sum+=query(p<<1,l,r);
    if(r>mid) sum+=query(p<<1|1,l,r);
    return sum;
}
signed main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(q--){
        int op;
        cin>>op;
        if(op==1){
            int l,r,x;
            cin>>l>>r>>x;
            update(1,l,r,x);
        }
        else if(op==2){
            int l,r;
            cin>>l>>r;
            cout<<query(1,l,r)<<endl;
        }
    }
    return 0;
}

by ICU152_QWQ_IS8 @ 2024-02-04 21:21:59

@Lovely_Cheese 哦我傻逼了

平时我写的时候都是lr表示当前改到什么地方询问记录用的是ql和qr（）

有点先入为主固有思维了（）

抱歉（）

by WilliamFranklin @ 2024-02-04 21:22:21

@Lovely_Cheese query 最后也要更新一下吧 tree[p].val=tree[p<<1].val+tree[p<<1|1].val;

by Lovely_Cheese @ 2024-02-04 21:23:17

@WilliamFranklin 查询为啥要更新

by ICU152_QWQ_IS8 @ 2024-02-04 21:25:31

@WilliamFranklin 查询不用