# 蒟蒻求助啊,最后三个点WR了,求大佬指点
查看原帖
# 蒟蒻求助啊,最后三个点WR了,求大佬指点
500707
久久君JUN楼主2021/5/14 20:39

蒟蒻求助啊,最后三个点WR了,求大佬指点

#include<stdio.h>
long long int n,m,a[100005];
struct tree{
	long long int l,r;
	long long int sum;
	long long int lazytag=0; 
}t[400020];
void pushdown(long long int i){
	if(t[i].lazytag!=0){
		t[2*i].lazytag+=t[i].lazytag;
		t[i*2+1].lazytag+=t[i].lazytag;
		t[i*2].sum+=t[i].lazytag*(t[2*i].r-t[i*2].l+1);
		t[2*i+1].sum+=t[i].lazytag*(t[2*i+1].r-t[i*2+1].l+1);
		t[i].lazytag=0;
	}
}
void build(long long int i,long long int l,long long int r){
	t[i].l=l; t[i].r=r;
	if(l==r){
		t[i].sum=a[l];
		return;
	}
	long long int mid=(l+r)/2;
	build(2*i,l,mid);
	build(2*i+1,mid+1,r);
	t[i].sum=t[2*i].sum+t[2*i+1].sum;
}
int sum(long long int i,long long int l,long long int r){
	if(t[i].l>=l&&t[i].r<=r){
		return t[i].sum;
	}
	pushdown(i);
	long long int s=0;
	if(t[i*2].r>=l) s=s+sum(2*i,l,r);
	if(t[i*2+1].l<=r) s=s+sum(2*i+1,l,r);
	return s;
}
void plus(long long int l,long long int r,long long int k,long long int i){
	if(t[i].l>=l&&t[i].r<=r){
		t[i].sum+=(t[i].r-t[i].l+1)*k;
		t[i].lazytag+=k;
		return;
	} 
	pushdown(i);
	if(t[i*2].r>=l) plus(l,r,k,2*i);
	if(t[i*2+1].l<=r) plus(l,r,k,2*i+1);
	t[i].sum=t[i*2].sum+t[i*2+1].sum;
}
int main(){
	long long int out;
	scanf("%lld %lld",&n,&m);
	getchar();
	for(long long int j=1;j<=n;j++){
			scanf("%lld",&a[j]);
		}
		build(1,1,n);
		getchar();
	for(long long int i=1;i<=m;i++){
		long long int tag,x,y,k;
		scanf("%lld",&tag);
		if(tag==1){
			scanf("%lld %lld %lld",&x,&y,&k);
			getchar();
			plus(x,y,k,1);
		}
		if(tag==2){
			scanf("%lld %lld",&x,&y);
			getchar();
			out=sum(1,x,y);
			printf("%lld\n",out);
		}
	}
	return 0;
}
2021/5/14 20:39
加载中...