社区讨论

玄学错误

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 条回复,欢迎继续交流。

正在加载回复...