线段树维护首项和公差,0pts求助qwq
查看原帖
线段树维护首项和公差,0pts求助qwq
824009
zzxj66楼主2023/9/5 22:06
#include<iostream>
#define ll long long
using namespace std;
int n,m;
ll kn[400050];
ll dn[400050];
ll A[400050];
void build(int l,int r,int rt){
	if(l==r){
		scanf("%lld",&A[rt]);
		return;
	}
	int mid = (l+r)>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
}
void push_down(int l,int r,int rt){
	if(kn[rt]!=0||dn[rt]!=0){
		kn[rt<<1]+=kn[rt];
		kn[rt<<1|1]+=kn[rt]+((l+r)>>1+1-l)*dn[rt];
		dn[rt<<1]+=dn[rt];
		dn[rt<<1|1]+=dn[rt];
		kn[rt]=dn[rt]=0;
	}
}
void add(int a,int b,ll k,ll d,int l,int r,int rt){
	if(a<=l&&b>=r){
		kn[rt]+=k+(l-a)*d;
		dn[rt]+=d;
		return;
	}
	push_down(l,r,rt);
	int mid = (l+r)>>1;
	if(a<=mid)add(a,b,k,d,l,mid,rt<<1);
	if(b>mid)add(a,b,k,d,mid+1,r,rt<<1|1);
}
ll find(int p,int l,int r,int rt){
	if(l==r){
		return A[rt]+kn[rt];
	}
	push_down(l,r,rt);
	int mid = (l+r)>>1;
	if(p<=mid)return find(p,l,mid,rt<<1);
	else return find(p,mid+1,r,rt<<1|1);
}
int main(){
	scanf("%d%d",&n,&m);
	build(1,n,1);
	while(m--){
		int op;
		scanf("%d",&op);
		if(op==1){
			int l,r,k,d;
			scanf("%d%d%lld%lld",&l,&r,&k,&d);
			add(l,r,k,d,1,n,1);
		}
		else{
			int p;
			scanf("%d",&p);
			ll c = find(p,1,n,1);
			printf("%lld\n",c);
		}
	}
}
2023/9/5 22:06
加载中...