线段树模板打挂了求助
查看原帖
线段树模板打挂了求助
449063
quitp楼主2022/1/22 15:49
#include<cstdio>
#define int long long
using namespace std;
const int maxn=1e5+1;
int n,m;
struct segment{
	int sum,lazy;
}t[4*maxn];
inline void downtag(int o,int l,int r,int mid){
	t[o<<1].sum+=t[o].lazy*(mid-l+1);
	t[o<<1|1].sum+=t[o].lazy*(r-mid);
	t[o<<1].lazy+=t[o].lazy;
	t[o<<1|1].lazy+=t[o].lazy;
	t[o].lazy=0;
}
inline void update(int o,int l,int r,int x,int y,int v){
	if(y<l||r<x) return ;
	if(x<=l&&r<=y){
		t[o].lazy+=v;
		t[o].sum+=v*(r-l+1);
		return ;
	}
	int mid=(l+r)>>1;
	downtag(o,l,r,mid);
	update(o<<1,l,mid,x,y,v);
	update(o<<1|1,mid+1,r,x,y,v);
	t[o].sum=t[o<<1].sum+t[o<<1|1].sum;
}
inline int query(int o,int l,int r,int x,int y){
	if(y<l||r<x) return 0;
	if(x<=l&&r<=y) return t[o].sum;
	int mid=(l+r)>>1;
	downtag(o,l,r,mid);
	int ret1=query(o<<1,l,mid,x,y);
	int ret2=query(o<<1|1,mid+1,r,x,y);
	return ret1+ret2;
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1,opt,x,y,k;i<=m;++i){
		scanf("%lld%lld%lld",&opt,&x,&y);
		if(opt==1){
			scanf("%lld",&k);
			update(1,1,n,x,y,k);
		} else {
			printf("%lld\n",query(1,1,n,x,y));
		}
	}
	return 0;
}

样例输出了三个 00,请 dalao 帮忙看看细节,谢谢。

2022/1/22 15:49
加载中...