社区讨论
玄学错误
P3372【模板】线段树 1参与者 3已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lo8ofnfm
- 此快照首次捕获于
- 2023/10/27 21:56 2 年前
- 此快照最后确认于
- 2023/10/27 21:56 2 年前
CPP
#include<bits/stdc++.h>
#define I using
#define love namespace
#define me std
I love me;
typedef long long ll;
typedef double db;
#define re register int
#define ce continue
#define pf printf
#define sf scanf
#define inf 1e9+10
#define lim 100010
#define mod 998244353
#define int ll
int gcd(int x,int y){return y?gcd(y,x%y):x;}
inline int rd(){
int x=0,f=1;char ch=getchar();
while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();}
while ('0'<=ch && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
int n,m;
int a[lim];
struct SegmentTree{
int l,r;
int sum,add;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define sum(x) tree[x].sum
#define add(x) tree[x].add
}tree[lim*4];
void build(int p,int l,int r){
l(p)=l,r(p)=r;
if(l==r){sum(p)=a[l];return;}
int mid=(l+r)>>1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
sum(p)=sum(p*2)+sum(p*2+1);
}
void spread(int p){
if(add(p)){
sum(p*2)+=add(p)*(r(p*2)-l(p*2)+1);
sum(p*2+1)+=add(p)*(r(p*2+1)-l(p*2+1)+1);
add(p*2)+=add(p);
add(p*2+1)+=add(p);
add(p)=0;
}
}
void change(int p,int l,int r,int d){
if(l<=l(p)&&r>=r(p)){
sum(p)+=d*(r(p)-l(p)+1);
add(p)+=d;
return;
}
spread(p);
int mid=(l(p)+r(p))>>1;
if(l<=mid)change(p*2,l,r,d);
if(r>mid)change(p*2+1,l,r,d);
sum(p)=sum(p*2)+sum(p*2+1);
}
int ask(int p,int l,int r){
if(l<=l(p)&&r>=r(p))return sum(p);
spread(p);
int mid=(l(p)+r(p))>>1;
int val=0;
if(l<=mid)val+=ask(p*2,l,r);
if(r>mid)val+=ask(p*2+1,l,r);
return val;
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)sf("%d",&a[i]);
build(1,1,n);
while(m--){
int op,l,r,d;
cin>>op;
if(op==1){cin>>l>>r>>d;change(1,l,r,d);}
else{cin>>l>>r;cout<<ask(1,l,r)<<"\n";}
}
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...