蒟蒻刚学线段树1ms WA+RE求助

__muiceredipS_ @ 2024-10-21 22:19:17

#include<bits/stdc++.h>
#define open(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
long long tree[400005];
long long b[400005];
long long a[100005];
int n,m;
void build(int s,int t,int p){
    if (s==t){
        tree[p]=a[s];
        return ;
    }
    long long m=s+t>>1;
    build(s,m,p<<1),build(m+1,t,p<<1+1);
    tree[s]=tree[s<<1]+tree[s<<1+1];
    return ;
}
void update(int &l,int &r,int c,int s,int t,int p){
    if (l<=s&&r>=t){
        tree[p]+=(t-s+1)*c,b[p]+=c;
        return ;
    }
    long long m=s+t>>1;
    if (b[p]!=0&&s!=t){
        tree[p<<1]+=(m-s+1)*b[p],b[p<<1]+=b[p];
        tree[p<<1+1]+=(t-m)*b[p],b[p<<1+1]+=b[p];
        b[p]=0;
    }
    if (l<=m)
        update(l,r,c,s,m,p<<1);
    if (r>m)
        update(l,r,c,m+1,t,p<<1);
    tree[p]=tree[p<<1]+tree[p<<1+1];
}
long long query(int &l,int &r,int s,int t,int p){
    if (l<=s&&r>=t)
        return tree[p];
    long long m=s+t>>1,sum=0;
    if (b[p]!=0){
        tree[p<<1]+=(m-s+1)*b[p],b[p<<1]+=b[p];
        tree[p<<1+1]+=(t-m)*b[p],b[p<<1+1]+=b[p];
        b[p]=0;
    }
    if (l<=m)
        sum+=query(l,r,s,m,p<<1);
    if (r>m)
        sum+=query(l,r,m+1,t,p<<1+1);
    return sum;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    build(1,n,1);
    for (int i=1;i<=m;i++){
        int op,x,y,k;
        cin>>op>>x>>y;
        if (op==1){
            cin>>k;
            update(x,y,k,1,n,1);
        }
        else
            cout<<query(x,y,1,n,1)<<endl;
    }
    return 0;
}

by __muiceredipS_ @ 2024-10-21 22:19:41

玄关

by da_ke @ 2024-10-21 22:31:43

@xuyian 位运算改一下 p<<1+1-》p<<1|1

by __muiceredipS_ @ 2024-10-22 19:09:05

@da_ke 感谢大佬RE解决了但还是WA

by _IceCream_ @ 2024-10-22 19:48:40

build 函数里面 tree[s]=tree[s<<1]+tree[s<<1+1]; 写错了。

by _IceCream_ @ 2024-10-22 19:49:37

update 函数里面右递归 update(l,r,c,m+1,t,p<<1); 写错了。

by __muiceredipS_ @ 2024-10-22 19:51:32

@IceCream 是这样吗

#include<bits/stdc++.h>
#define open(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
long long tree[400005];
long long b[400005];
long long a[100005];
int n,m;
void build(int s,int t,int p){
    if (s==t){
        tree[p]=a[s];
        return ;
    }
    long long m=s+t>>1;
    build(s,m,p<<1),build(m+1,t,p<<1|1);
    tree[s]=tree[s<<1]+tree[s<<1|1];
    return ;
}
void update(int &l,int &r,int c,int s,int t,int p){
    if (l<=s&&r>=t){
        tree[p]+=(t-s+1)*c,b[p]+=c;
        return ;
    }
    long long m=s+t>>1;
    if (b[p]!=0&&s!=t){
        tree[p<<1]+=(m-s+1)*b[p],b[p<<1]+=b[p];
        tree[p<<1|1]+=(t-m)*b[p],b[p<<1|1]+=b[p];
        b[p]=0;
    }
    if (l<=m)
        update(l,r,c,s,m,p<<1);
    if (r>m)
        update(l,r,c,m+1,t,p<<1|1);
    tree[p]=tree[p<<1]+tree[p<<1|1];
}
long long query(int &l,int &r,int s,int t,int p){
    if (l<=s&&r>=t)
        return tree[p];
    long long m=s+t>>1,sum=0;
    if (b[p]!=0){
        tree[p<<1]+=(m-s+1)*b[p],b[p<<1]+=b[p];
        tree[p<<1|1]+=(t-m)*b[p],b[p<<1|1]+=b[p];
        b[p]=0;
    }
    if (l<=m)
        sum+=query(l,r,s,m,p<<1);
    if (r>m)
        sum+=query(l,r,m+1,t,p<<1|1);
    return sum;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    build(1,n,1);
    for (int i=1;i<=m;i++){
        int op,x,y,k;
        cin>>op>>x>>y;
        if (op==1){
            cin>>k;
            update(x,y,k,1,n,1);
        }
        else
            cout<<query(x,y,1,n,1)<<endl;
    }
    return 0;
}

by _IceCream_ @ 2024-10-22 19:53:24

额 build 函数里面 tree[s]=tree[s<<1]+tree[s<<1|1]; 还是错的哥们。

您拿区间节点更新线段树啊。

by __muiceredipS_ @ 2024-10-22 20:01:36

@IceCream 本蒟蒻实在是太蒻了所以能详细讲讲吗大佬

by _IceCream_ @ 2024-10-22 20:03:24

@xuyian 额你 s 是当前访问的区间的左节点啊，p 才是你遍历的指向线段树数组的下标啊。

你更新肯定使用线段树数组下标更新而不是拿区间节点去更新吧。

by __muiceredipS_ @ 2024-10-22 20:04:47

@IceCream 感谢大佬已关