萌新刚学OI求调全RE线段树
查看原帖
萌新刚学OI求调全RE线段树
486727
IaLWH楼主2024/8/6 20:28

写完后代码太乱看不出问题力(悲

#include<stdio.h>
#define ll long long
struct node{
	ll sum,lazy;
	int l,r;
}tree[114514<<2];

ll data[114514];
int n,m;

inline void build(int i,int l,int r){
	tree[i].l=l;
	tree[i].r=r;
	if(l==r){
		tree[i].sum=data[i];
		return;
	}
	ll mid=l+r>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
	tree[i].sum=tree[i<<1].sum+tree[(i<<1)+1].sum;
}
inline void plus(int l,int r,ll c,int L,int R,int i){
	    //[l,r]+c changing  [L,R]node including i index now
	if(l<=L&&r>R){
		tree[i].sum+=(R-L+1)*c;   //屯好所有子节点的数 
		tree[i].lazy+=c;          //懒标记 
		return;
	}
	ll mid=L+R>>1;
	if(tree[i].lazy&&L!=R){     //懒标记非空且非叶节点 
		tree[i<<1].sum+=tree[i].lazy*(mid-L+1);//左边加上数 
		tree[i<<1|1].sum+=tree[i].lazy*(R-mid);//右边加上数 
		tree[i<<1].lazy+=tree[i].lazy;
		tree[i<<1|1].lazy+=tree[i].lazy;       //左右传下懒标记 
		tree[i].lazy=0;    //clear lazy mark
	}
	if(l<=mid)
		plus(l,r,c,L,m,i<<1);
	if(r>mid)
		plus(l,r,c,mid+1,R,i<<1|1);
	tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;  //merge
}
ll search(int l,int r,int L,int R,int i){
	if(l<=L&&r>R)
		return tree[i].sum;
	ll mid=L+R>>1;
	if(tree[i].lazy){
		tree[i<<1].sum+=tree[i].lazy*(mid-L+1);
		tree[i<<1|1].sum+=tree[i].lazy*(R-mid);//右边加上数 
		tree[i<<1].lazy+=tree[i].lazy;
		tree[i<<1|1].lazy+=tree[i].lazy;       //左右传下懒标记 
		tree[i].lazy=0;    //clear lazy mark
	}
	ll t;
	if(l<=mid)
		t=search(l,r,L,mid,i<<1);
	if(r>mid)
		t+=search(l,r,mid+1,R,i<<1|1);
	return t;
}
int main(){
	char command;
	int x,y;
	ll k;
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)
		scanf("%lld",data+i);
	build(1,1,n);
	for(int i=0;i<m;i++){
		command=getchar();
		if(command==49){
			scanf("%d%d%lld",&x,&y,&k);
			plus(x,y,k,1,n,1);
		}else{
			scanf("%d%d",&x,&y);
			printf("%lld\n",search(x,y,1,n,1));
		}
	}
	return 0;
}
2024/8/6 20:28
加载中...