代码求调(悬关!!)
查看原帖
代码求调(悬关!!)
574921
Dress楼主2024/3/9 19:39

各位dalao帮帮忙吧

#include<bits/stdc++.h>
#define N 100010
using namespace std;
long long n,m,k,a[N];
struct tree{
	long long l,r;
	long long data,sum;
}t[N*4];
void updata(long long p){
	t[p].data=t[p*2].data+t[p*2+1].data;
}	
void down(long long p){
	if(t[p].l!=0){
		t[p*2].sum+=t[p].sum;
		t[p*2+1].sum+=t[p].sum;
		t[p*2].data+=t[p].sum*(t[p*2].r-t[p*2].l+1);
		t[p*2+1].data+=t[p].sum*(t[p*2+1].r-t[p*2+1].l+1);
		t[p].sum=0;
	}
	updata(p);
}
void build(long long p,long long l,long long r){
	t[p].l=l,t[p].r=r;
	if(l==r){
		t[p].data=a[l];return;
	}
	long long mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	updata(p);
}
void ff(long long p,long long l,long long r,long long k){
	if(l<=t[p].l&&t[p].r<=r){
		t[p].data+=(t[p].r-t[p].l+1)*k;
		t[p].sum+=k;
		return ;
	}
	down(p);
	if(t[p*2].r>=l){
		ff(p*2,l,r,k);
	}
	if(t[p*2+1].l<=r){
		ff(p*2+1,l,r,k);
	}
	updata(p);
}
long long ask(long long p,long long l,long long r){
	if(l<=t[p].l&&t[p].r<=r){
		return t[p].data;
	}
	if(t[p].l>r||t[p].r<l){
		return 0;
	}
	down(p);
	long long ans=0;
	if(t[p*2].r>=l){
		ans+=ask(p*2,l,r);
	}
	if(t[p*2+1].l<=r){
		ans+=ask(p*2+1,l,r);
	}
	return ans;
}
int main(){
	cin>>n>>m;
	for(long long i=1;i<=n;++i){
		cin>>a[i];
	}
	build(1,1,n);
	long long x,y,z;
	for(long long i=1;i<=m;++i){
		cin>>k>>x>>y;
		if(k==1){
			cin>>z;
			ff(1,x,y,z);
			continue;
		}
		cout<<ask(1,x,y);
	}
	return 0;
}
2024/3/9 19:39
加载中...