求大佬指正,只有9分
查看原帖
求大佬指正,只有9分
374597
Owen惠英贤楼主2023/9/1 13:31
#include<bits/stdc++.h>
using namespace std;
long long n,m,a[100005],b[100005],k,d,be,bad,sum[1000005],ans,lazy[1000005],eff;
struct st{
	int l;
	int r;
};
st tr[1000005];
void build(int u,int l,int r)
{
	tr[u].l=l;tr[u].r=r;
	if(l==r){
		sum[u]=b[l];
		return;
	}
	int mid=(l+r)/2;
	build(u*2,l,mid);
	build(u*2+1,mid+1,r);
	sum[u]=sum[u*2]+sum[u*2+1];
}
void check(int u,int l,int r)
{
	sum[u]+=(r-l+1)*d;
	if(tr[u].l==l&&tr[u].r==r){
		lazy[u]+=d;
		return;
	}
	int mid=(tr[u].l+tr[u].r)/2;
	if(l<=mid)
	{
		if(r>mid){
			check(u*2,l,mid);
			check(u*2+1,mid+1,r); 
		}
		else{
			check(u*2,l,r);
		}
	}
	else{
		check(u*2+1,l,r); 
	}
}
void pushdown(int u)
{
	sum[u*2]+=(tr[u*2].r-tr[u*2].l+1)*lazy[u];
	sum[u*2+1]+=(tr[u*2+1].r-tr[u*2+1].l+1)*lazy[u];
	lazy[u*2]+=lazy[u];lazy[u*2+1]+=lazy[u];
	lazy[u]=0;
}
void out(int u,int l,int ed)
{
	
	if(tr[u].l==l&&tr[u].r==ed){
		ans+=sum[u];
		return;
	}
	if(lazy[u]!=0){
		pushdown(u);
	}
	int mid=(tr[u].l+tr[u].r)/2;
	if(l<=mid){
		if(ed>mid){
			out(u*2,l,mid);
			out(u*2+1,mid+1,ed);
		}
		else{
			out(u*2,l,ed);
		}
	}
	else{
		out(u*2+1,l,ed);
	}
}
void last(int u)
{
	int p=0;
	if(be>=tr[u].l&&be<=tr[u].r){
		sum[u]+=k-d;
		p=1;
	}
	if(bad>=tr[u].l&&bad<=tr[u].r){
		sum[u]-=eff;
		p=1;
	}
	if(tr[u].l==tr[u].r) return;
	if(p==0) return;
	last(u*2);
	last(u*2+1);
}
int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		b[i]=a[i]-a[i-1];//差分数组 
	}
	build(1,1,n);
	while(--m>=0){
		int p,l,r,end;
		scanf("%d",&p);
		if(p==1){
			scanf("%d%d%d%d",&l,&r,&k,&d);
			be=l,bad=r+1;
			eff=k+(r-l)*d;
			check(1,l,r);
			last(1);
		}
		else{
			scanf("%d",&end);
			out(1,1,end);
			printf("%lld",ans);
			cout<<endl;
			ans=0;
		}
	}
 } 
2023/9/1 13:31
加载中...