线段树求助
查看原帖
线段树求助
1199534
ycy1124楼主2024/6/25 17:01
#include<bits/stdc++.h>
using namespace std;
struct Node{
	long long w,k,d,bj;
}a[8000001];
long long b[500001];
long long n,m;
void work(int p,int l,int r){
	int mid=(l+r)>>1;
	if(l==r){
		a[p].w=b[l];
		return;
	}
	work(p*2,l,mid);
	work(p*2+1,mid+1,r);
	a[p].w=a[p*2].w+a[p*2+1].w;
}
void work1(int p,int l,int r,int x,int y,int k,int d){
	int mid=(l+r)>>1;
	if(l>=x&&r<=y){
		a[p].w+=(a[p].k+a[p].k+(r-l)*a[p].d)*(r-l+1)/2;
		a[p].k=k;
		a[p].d=d;
		return;
	}
	a[p].w+=(k+k+((min(r,y)-max(x,l))*d)*(min(r,y)-max(x,l)+1))/2;
	if(x>mid){
		work1(p*2+1,mid+1,r,x,y,k+(mid+1-min(x,l))*d,d);
	}
	else if(y<=mid){
		work1(p*2,l,mid,x,y,k,d);
	}
	else{
		work1(p*2,l,mid,x,y,k,d);
		work1(p*2+1,mid+1,r,x,y,k+(mid+1-min(x,l))*d,d);
	}
}
void read(long long &x){
	x=0;
	int f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	x*=f;
}
long long ans(int p,int l,int r,int x){
	int mid=(l+r)>>1;
	if(a[p].d!=0||a[p].k!=0){
		a[p].w+=(a[p].k+(r-l)*a[p].d+a[p].k)*(r-l+1)/2;
		if(r-l!=0){
			a[2*p].w+=(a[2*p].k+a[2*p].k+(r-l)*a[2*p].d)*(r-l+1)/2;
			a[2*p].k=a[p].k;
			a[2*p].d=a[p].d;
			a[2*p+1].w+=(a[2*p+1].k+a[2*p+1].k+(r-l)*a[2*p+1].d)*(r-l+1)/2;
			a[2*p+1].k=a[p].k+(mid+1-min(l,x))*a[p].d;
			a[2*p+1].d=a[p].d;
			a[p].k=0;
			a[p].d=0;
		}
		else{
			return a[p].w+a[p].k;
		}
	}
	if(x>mid){
		return ans(2*p+1,mid+1,r,x);
	}
	else{
		return ans(2*p,l,mid,x);
	}
}
int main(){
	read(n);
	read(m);
	for(int i=1;i<=n;i++){
		read(b[i]);
	}
	for(int i=1;i<=m;i++){
		long long op,l,r,k,d;
		read(op);
		if(op==1){
			read(l);
			read(r);
			read(k);
			read(d);
			work1(1,1,n,l,r,k,d);
		}
		else{
			scanf("%d",&l);
			printf("%lld\n",ans(1,1,n,l));
		}
	}
	work(1,1,n);
	return 0;
}
2024/6/25 17:01
加载中...