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,已关