P3372 【模板】线段树 1

emo_zkt @ 2024-10-25 18:02:46

连样例也不对,求调,orz

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N];
struct nod{
    int le,ri,lz,val;
}tr[N<<2];
void pu(int root){
    tr[root].val=tr[root<<1].val+tr[root<<1|1].val;
}
void spr(int p){
    if(tr[p].lz!=0){
        int l=tr[p].lz;
        tr[p<<1].lz+=l;
        tr[p<<1].val+=(tr[p<<1].ri-tr[p<<1].le+1)*l;
        tr[p<<1|1].lz+=l;
        tr[p<<1|1].val+=(tr[p<<1|1].ri-tr[p<<1|1].le+1)*l;
        tr[p].lz=0;
    }
}
void build(int root,int l,int r){
    tr[root].le=l,tr[root].ri=r;
    if(l==r){
        tr[l].val=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(root<<1,l,mid);
    build(root<<1|1,mid+1,r);
    pu(root);
}
void updateq(int p,int l,int r,int k){
    if(tr[p].le>=l&&tr[p].ri<=r){
        tr[p].val+=(tr[p].ri-tr[p].le+1)*k;
        tr[p].lz+=k;
        return;
    }
    spr(p);
    int mid=(tr[p].le+tr[p].ri)>>1;
    if(l<=mid)updateq(p<<1,l,r,k);
    if(r>mid)updateq(p<<1|1,l,r,k);
    pu(p);
}
void updated(int p,int x,int k){
    if(tr[p].le==tr[p].ri){
        tr[p].val+=k;
        return;
    }
    int mid=(tr[p].le+tr[p].ri)>>1;
    if(x<=mid)updated(p<<1,x,k);
    if(x>mid)updated(p<<1|1,x,k);
    pu(p);
}
int que(int p,int l,int r){
    if(tr[p].le>=l&&tr[p].ri<=r)return tr[p].val;
    int mid=(tr[p].le+tr[p].ri)>>1,ans=0;
    if(l<=mid)ans+=que(p<<1,l,r);
    if(r>mid)ans+=que(p<<1|1,l,r);
    return ans;
}
int main(){
    int n,m;
    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 b,x,y,k;
        cin>>b>>x>>y;
        if(b==1){
            cin>>k;
            updateq(1,x,y,k);
        }
        else{
            cout<<que(1,x,y)<<'\n';
        }
    }
    return 0;
}

by LaiJinYi @ 2024-10-25 18:09:29

你que没spr


by LaiJinYi @ 2024-10-25 18:10:14

还有就是建议开 long long。


by wangziyue_AK @ 2024-10-25 18:12:25

build里应该是

tr[root].val=a[l];

你写了

tr[l].val=a[l];

by wangziyue_AK @ 2024-10-25 18:14:04

然后再补上que里的spr就能过样例了


by emo_zkt @ 2024-10-25 21:42:36

@LaiJinYi @wangziyue_AK 谢谢


by 湖南省队御用绫厨TM_Sharweek @ 2024-11-29 11:52:24

泠珞keai


|