yangjunhan1 @ 2023-05-26 13:31:12
#include<bits/stdc++.h>
using namespace std;
int n,a[500000],lazy[200000],t[200000],fl,fr,v,m,q;
void build(int l,int r,int ro){//建树
if(l==r){//最小节点,返回值
t[ro]=a[l];
return ;
}
int mid=l+r>>1;
build(l,mid,ro*2);
build(mid+1,r,ro*2+1);//左右子树
t[ro]=t[ro*2]+t[ro*2+1];
}
int gs(int l,int r,int ro){//区间求和
if(fl<=l && r<=fr) return t[ro];//完全包含,直接返回
int mid=l+r>>1,s=0;
if(fl<=mid) s+=gs(l,mid,ro*2);//与左子树有关
if(fr>mid) s+=gs(mid+1,r,ro*2+1);//与右子树有关;
return s;
}
void qjxg(int l,int r,int ro){//区间修改(加上v)
if(fl<=l && r<=fr){//完全属于,直接加
t[ro]=(r-l+1)*v,lazy[ro]+=v;
return ;
}
int mid=l+r>>1;
if(lazy[ro]){//懒标记还在
t[ro*2]+=lazy[ro]*(mid-l+1),lazy[ro*2]+=lazy[ro];//左子树值加v,懒标记传递
t[ro*2+1]+=lazy[ro]*(r-mid),lazy[ro*2+1]+=lazy[ro];//右子树……
lazy[ro]=0;//懒标记归零
}
if(fl<=mid) qjxg(l,mid,ro*2);
if(fr>mid) qjxg(mid+1,r,ro*2+1);
t[ro]=t[ro*2]+t[ro*2+1];
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
build(1,n,1);
while(m--){
scanf("%d %d %d",&q,&fl,&fr);
if(q==1){
scanf("%d",&v);
qjxg(1,n,1);
}
else cout<<gs(1,n,1)<<endl;
memset(lazy,0,sizeof(lazy));
}
return 0;
}
by Nwayy @ 2023-05-26 13:47:30
@yangjunhan1 区间修改是 +=,其次 gs 函数里也要 pushdown
by yangjunhan1 @ 2023-05-26 13:48:59
@winds888 pushdown是什么意思?
by Nwayy @ 2023-05-26 14:12:16
@yangjunhan1 标记下放,也就是你的lazy
by yangjunhan1 @ 2023-05-26 14:14:14
@winds888 哦,可是我现在加了,还是有问题
by Nwayy @ 2023-05-26 14:16:50
@yangjunhan1 再重申一次哈,问题如下:
懒标记在 gs 函数里也要下放;
区间加那里是 +=;
开 long long
by yangjunhan1 @ 2023-05-26 14:21:19
@winds888 哦,谢谢,现在应该没问题了