xzy__xzy @ 2022-12-08 21:21:31
#include<bits/stdc++.h>
#define int long long
#define l(x) 2*x
#define r(x) 2*x+1
using namespace std;
int n,m,a[100012],gg[100004];
int op,xi,yi,ki;
struct g{
int x,y,p;
}t[470100];
void build(int id,int xx,int yy){
if(xx==yy) {gg[xx]=id,t[id].x=t[id].y=xx,t[id].p=a[xx];return;
}
else if(xx>yy) return;
else{
int mid =int((xx+yy)/2);
build(l(id),xx,mid);
build(r(id),mid+1,yy);
t[id].x=xx,t[id].y=yy,t[id].p=t[l(id)].p+t[r(id)].p;
}
}
void rs(int id,int xx,int yy,int kk){
if(xx>yy)return;
else{
t[id].p+=(yy-xx+1)*kk;
rs(l(id),max(xx,t[l(id)].x),min(yy,t[l(id)].y),kk);
rs(r(id),max(xx,t[r(id)].x),min(yy,t[r(id)].y),kk);
}
}
int q(int x,int y,int id){
if(x==y)
return t[gg[x]].p;
else if(x>y)
return 0;
else
return q(max(x,t[l(id)].x),min(y,t[l(id)].y),l(id))+q(max(x,t[r(id)].x),min(y,t[r(id)].y),r(id));
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
build(1,1,n);
for(int i=1;i<=m;i++){
scanf("%d",&op);
if(op==1){
scanf("%lld%lld%lld",&xi,&yi,&ki);
rs(1,xi,yi,ki);
}
else{
scanf("%lld%lld",&xi,&yi);
printf("%lld\n",q(xi,yi,1));
}
}
return 0;
}
by OoHappyoO @ 2022-12-08 22:07:06
忘记写懒标记了?
by OoHappyoO @ 2022-12-08 22:07:39
@xzy__xzy 忘记写懒标记了?
by xzy__xzy @ 2022-12-09 20:02:45
@OoHappyoO请教一下,我没有用lazytag, 为什么前7个点过了,最后三个点是re而不是wa