感觉写的没错但是就过了一个点。。。
查看原帖
感觉写的没错但是就过了一个点。。。
212172
Dubhe_楼主2021/9/26 20:00

蹲一个大佬帮忙调一下,人要没了。。。

#include<bits/stdc++.h>
using namespace std;
long long T[400005];
long long A[400005];
int n,m,ord,lin,rin;
long long num;
long long Lazy[200005];
void PutDown(int k,int l,int r){ //下放Lazy标记
	if(Lazy[k]){
		Lazy[k*2]+=Lazy[k];
		Lazy[k*2+1]+=Lazy[k];
		int mid=(l+r)/2;
		T[k*2]+=(mid-l+1)*Lazy[k];
		T[k*2+1]+=(r-mid)*Lazy[k];
		Lazy[k]=0;
	}
} //下放懒标记
void BuildTree(int k,int l,int r){
	if(l==r) T[k]=A[l]; //边界情况判断 
	else{
		int mid=(l+r)/2;
		BuildTree(k*2,l,mid);
		BuildTree(k*2+1,mid+1,r); //递归建树
		T[k]=T[k*2]+T[k*2+1]; //更新当前节点值
	}
}
void Update(int k,int l,int r){
	if(lin<=l&&rin>=r){ //完全包含于修改区间 
		T[k]+=num*(r-l+1); //直接更新该点的值
		Lazy[k]+=num;  //更新该点Lazy数组 
		return;
	}
	if(l>rin||r<lin) return; //完全不包含的直接跳过
	//下面是有一部分包含的
	int mid=(l+r)/2;
	if(lin<=mid) Update(k*2,l,mid); //更新左区间
	if(rin>mid) Update(k*2+1,mid+1,r); //更新右区间
	T[k]=T[k*2]+T[k*2+1]; //更新当前的数组 
}
long long GetSum(int k,int l,int r){
	long long ans=0; //定义答案数组
	if(lin<=l&&rin>=r){
		return T[k]; //如果完全包含则直接返回
	} 
	if(l>rin||r<lin) return 0; //完全不包含也直接返回
	int mid=(l+r)/2;
	PutDown(k,l,r); //用到子树的时候下放懒标记
	if(lin<=mid) ans+=GetSum(k*2,l,mid);
	if(rin>mid) ans+=GetSum(k*2+1,mid+1,r);//因为右侧从mid+1开始
	//所以mid不在r的考虑范围内
	return ans;//返回答案
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&A[i]);
	}
	BuildTree(1,1,n);
	for(int i=1;i<=m;i++){
		scanf("%d",&ord);
		if(ord==1){
			scanf("%d%d%lld",&lin,&rin,&num);
			Update(1,1,n);
		}
		else{
			scanf("%d%d",&lin,&rin);
			long long ans=GetSum(1,1,n);
			printf("%lld\n",ans);
		}
	}
}
2021/9/26 20:00
加载中...