wosyioq_1367 @ 2024-07-18 14:22:29
#include<bits/stdc++.h>
using namespace std;
const int M=1e5+10;
int n,a[M],m;
struct node{
int s,t,p;
}b[4*M];
void pushup(int p){b[p].s=b[p*2].s+b[p*2+1].s;}
void Tag(int p,int z,int l,int r){b[p].t+=z,b[p].s+=(r-l+1)*z;}
void pushdown(int p,int l,int r){
if(b[p].t){
Tag(p*2,b[p].t,l,r);
Tag(p*2+1,b[p].t,l,r);
b[p].t=0;
}
}
int sum(int p,int l,int r,int x,int y){
if(x<=l&&r<=y)return b[p].s;
pushdown(p,l,r);
int mid=(l+r)>>1,ans=0;
if(x<=mid)ans+=sum(p*2,l,mid,x,y);
cout<<ans<<"\n";
if(mid<y)ans+=sum(p*2+1,mid+1,r,x,y);
cout<<ans<<"\n";
return ans;
}
void build(int p,int l,int r){
if(l==r)return b[p].s=a[l],void();
int mid=(l+r)>>1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
pushup(p);
}
void upd(int p,int l,int r,int x,int y,int z){
if(l>=x&&r<=y)return Tag(p,z,l,r);
pushdown(p,l,r);
int mid=(l+r)>>1;
if(x<=mid)upd(p*2,l,mid,x,y,z);
if(mid<y)upd(p*2+1,mid+1,r,x,y,z);
pushup(p);
}
int main(){
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 op,x,y,k;
cin>>op;
if(op==1){
cin>>x>>y>>k;
upd(1,1,n,x,y,k);
}else{
cin>>x>>y;
cout<<sum(1,1,n,x,y)<<endl;
}
}
return 0;
}
样例输出:
11
8
20
我的输出:
11
8
23
by wosyioq_1367 @ 2024-07-18 14:23:06
样例输入:
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
by zzy0618 @ 2024-07-18 16:06:01
@wosyioq_1367
push_down
写错了void pushdown(int p,int l,int r){
if(b[p].t){
int mid=(l+r)>>1;
Tag(p*2,b[p].t,l,mid);
Tag(p*2+1,b[p].t,mid+1,r);
b[p].t=0;
}
}
要看数据范围,这题要用 long long
把调试信息删掉
by wosyioq_1367 @ 2024-07-18 16:11:19
thanks,已AC此贴结