关于线段树
  • 板块学术版
  • 楼主_yjh
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/1/30 19:31
  • 上次更新2023/11/5 04:07:54
查看原帖
关于线段树
222104
_yjh楼主2021/1/30 19:31

刚刚打模板时,突发奇想删掉了区间修改中的下传标记,想不出有任何问题,但交上后只有10pts(改的满分代码),有没有大佬可以讲一下删掉这一行对程序有什么影响,谢谢了。

#include<iostream>
using namespace std;
long long n,m,a[100005],Node[4*100005],lazy[4*100005];
long long num,sum,ll,rr;
void Push(long long t,long long len) {
	if(lazy[t]) {
	    Node[2*t]+=(len-len/2)*lazy[t];
	    lazy[2*t]+=lazy[t];
	    Node[2*t+1]+=(len/2)*lazy[t];
	    lazy[2*t+1]+=lazy[t];
	    lazy[t]=0;
	}
}
void Build(long long t,long long l,long long r) {
	if(l==r) {
		Node[t]=a[l];
		return ;
	}
	long long mid=(l+r)/2;
	Build(2*t,l,mid);
	Build(2*t+1,mid+1,r);
	Node[t]=Node[2*t]+Node[2*t+1];
}
void Query(long long t,long long l,long long r) {
	if(ll<=l&&r<=rr) {
		sum+=Node[t];
		return ;
	}
	Push(t,r-l+1);
	long long mid=(l+r)/2;
	if(ll<=mid) Query(2*t,l,mid);
	if(rr>=mid+1) Query(2*t+1,mid+1,r);
}
void Add(long long t,long long l,long long r) {
	if(ll<=l&&r<=rr) {
		Node[t]+=(r-l+1)*num;
		lazy[t]+=num;
		return ;
	}
	Push(t,r-l+1); //就是这一行
	long long mid=(l+r)/2;
	if(ll<=mid) Add(2*t,l,mid);
	if(rr>=mid+1) Add(2*t+1,mid+1,r);
	Node[t]=Node[2*t]+Node[2*t+1];
}
int main() {
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(long long i=1;i<=n;i++) cin>>a[i];
	Build(1,1,n);
	while(m--) {
		long long team;
		cin>>team>>ll>>rr;
		if(team==1) {
			cin>>num;
			Add(1,1,n);
		}
		else {
			sum=0;
			Query(1,1,n);
			cout<<sum<<'\n';
		}
	}
	return 0;
}

查询的时候下传不是一样吗

2021/1/30 19:31
加载中...