Chtholly_is_cute @ 2024-08-25 16:46:01
code:
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000001;
struct tree{
int l,r;
long long val,upd;
}a[MAXN<<2];//鍏堝簭閬嶅巻
long long b[MAXN];
void build(int l,int r,int cur){
a[cur].l=l;
a[cur].r=r;
if(l==r){
a[cur].val=b[l];
return;
}
int mid=l+r>>1;
build(l,mid,cur*2);
build(mid+1,r,cur*2+1);
a[cur].val=a[cur<<1].val+a[cur*2+1].val;
return ;
}
void pushdown(int cur){
if(a[cur].upd){
a[cur<<1].val+=a[cur].upd*(a[cur<<1].r-a[cur<<1].l+1);
a[(cur<<1)+1].val+=a[cur].upd*(a[cur*2+1].r-a[cur*2+1].l+1);
a[cur*2].upd+=a[cur].upd;
a[cur*2+1].upd+=a[cur].upd;
a[cur].upd=0;
}
}
void fill(int cur,int x,int y,int z){
if(x<=a[cur].l&&y>=a[cur].r){
a[cur].val+=(long long)z*(a[cur].r-a[cur].l+1);
a[cur].upd+=z;
return;
}
pushdown(cur);
int mid=a[cur].l+a[mid].r;
mid>>=1;
if(x<=mid)fill(cur>>1,x,y,z);
if(y>mid)fill((cur>>1)+1,x,y,z);
a[cur].val=a[cur<<1].val+a[(cur<<1)+1].val;
}
long long ask(int cur,int x,int y){
if(x<=a[cur].l&&y>=a[cur].r)return a[cur].val;
pushdown(cur);
int mid=a[cur].r-a[cur].l+1;
long long ans=0;
if(x<=mid)ans+=ask(cur*2,x,y);
if(y>mid)ans+=ask(cur*2+1,x,y);
return ans;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",b+i);
build(1,n,1);
for(int i=1;i<=m;i++){
int q,w,e,r;
scanf("%d",&q);
if(q==1){
scanf("%d%d%d",&w,&e,&r);
fill(1,w,e,r);
}
if(q==2){
scanf("%d%d",&w,&e);
cout<<ask(1,w,e)<<endl;
}
}
return 0;
}by _ZHZ_ @ 2024-09-08 22:01:39
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,x,y,k,op,a[N];
struct{
int Left,Right;
long long data,add;
}t[N*4];
void Build_Tree(int p,int Left,int Right){
t[p].Left=Left;
t[p].Right=Right;
if(Left==Right){
t[p].data=a[Left];
return;
}
else{
int mid=(Left+Right)/2;
Build_Tree(p*2,Left,mid);
Build_Tree(p*2+1,mid+1,Right);
t[p].data=t[p*2].data+t[p*2+1].data;
}
}
void spread(int p){
if(t[p].add){
t[p*2].data+=t[p].add*(t[p*2].Right-t[p*2].Left+1);
t[p*2+1].data+=t[p].add*(t[p*2+1].Right-t[p*2+1].Left+1);
t[p*2].add+=t[p].add;
t[p*2+1].add+=t[p].add;
t[p].add=0;
}
}
void Change_Value(int p,int L,int R,int d){
if(L<=t[p].Left&&R>=t[p].Right){
t[p].data+=(long long)d*(t[p].Right-t[p].Left+1);
t[p].add+=d;
return;
}
spread(p);
int mid=(t[p].Left+t[p].Right)/2;
if(L<=mid) Change_Value(p*2,L,R,d);
if(R>mid) Change_Value(p*2+1,L,R,d);
t[p].data=t[p*2].data+t[p*2+1].data;
}
long long Ask(int p,int Left,int Right){
if(Left<=t[p].Left&&Right>=t[p].Right) return t[p].data;
spread(p);
int mid=(t[p].Left+t[p].Right)/2;
long long ans=0;
if(Left<=mid) ans+=Ask(p*2,Left,Right);
if(Right>mid) ans+=Ask(p*2+1,Left,Right);
return ans;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
Build_Tree(1,1,n);
for(int i=1;i<=m;i++){
scanf("%d",&op);
if(op==1){
scanf("%d%d%d",&x,&y,&k);
Change_Value(1,x,y,k);
}
else{
scanf("%d%d",&x,&y);
printf("%lld\n",Ask(1,x,y));
}
}
return 0;
}