未知的WA! dalao求条,悬1

P3372 【模板】线段树 1

forever516 @ 2024-09-03 20:14:14

线段树太难调了,求大佬指出错误。 (蒟蒻未过样例)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll n,m,t[N<<2],ta[N<<2],a[N];
ll ls(ll l){return (l<<1);}
ll rs(ll r){return (r<<1)|1;}
void push(ll p){t[p]=t[ls(p)]+t[rs(p)];}
void bu(ll p,ll pl,ll pr){
    ta[p]=0;
    if(pl==pr){
        t[p]=a[pl];
        return ;
    }
    ll mid=(pl+pr)>>1;
    bu(ls(p),pl,mid);
    bu(ls(p),mid+1,pr);
    push(p);
}
void at(ll p,ll pl,ll pr,ll d){
    ta[p]+=d;
    t[p]+=d*(pr-pl+1);
}
void pd(ll p,ll pl,ll pr){
    if(ta[p]){
        ll mid=(pl+pr)>>1;
        at(ls(p),pl,mid,ta[p]);
        at(rs(p),mid+1,pr,ta[p]);
        ta[p]=0;
    }
}
void ud(ll L,ll R,ll p,ll pl,ll pr,ll d){
    if(L<=pl&&pr<=R){
        at(p,pl,pr,d);
        return ;
    }
    pd(p,pl,pr);
    ll mid=(pl+pr)>>1;
    if(L<=mid)ud(L,R,ls(p),pl,mid,d);
    if(R>mid)ud(L,R,rs(p),mid+1,pr,d);
    push(p);
}
ll qu(ll L,ll R ,ll p,ll pl,ll pr){
    if(pl>=L&&pr<=R)return t[p];
    pd(p,pl,pr);
    ll re=0,mid=(pl+pr)>>1;
    if(L<=mid)re+=qu(L,R,ls(p),pl,mid);
    if(R>mid)re+=qu(L,R,rs(p),mid+1,pr);
    return re;
}
int main(){
    cin>>n>>m;
    for(ll i=1;i<=n;i++)cin>>a[i];
    bu(1,1,n);
    while(m--){
        ll q,L,R,d;
        cin>>q;
        if(q==1){
            cin>>L>>R>>d;
            ud(L,R,1,1,n,d);
        }else{
            cin>>L>>R;
            cout<<qu(L,R,1,1,n)<<"\n";
        }
    }

    return 0;
}

by forever516 @ 2024-09-03 20:17:24

快疯了!!!


by SuperAlex4 @ 2024-09-03 20:39:19

11 行 rs(p) 写成 ls(p)


by SuperAlex4 @ 2024-09-03 20:40:02

17 行*


by hez_EX @ 2024-09-03 20:40:40

bu 函数内(第 17 行)ls 改为 rs 就过了……


by forever516 @ 2024-09-04 16:12:04

thx,已关


|