【玄关】线段树36pts马蜂优良求调
查看原帖
【玄关】线段树36pts马蜂优良求调
808454
NOI__CCF楼主2024/7/10 21:14
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
ll n,m,a[N],c[N]; 
struct Tree{
	ll val,lazy;
}t[4*N];
void pushup(ll node){
	t[node].val=t[node<<1].val+t[node<<1|1].val;	
}
void build(ll l,ll r,ll node){
	t[node].lazy=0;
	if(l==r){
		t[node].val=c[l];
		return;
	}
	ll mid=(l+r)>>1;
	build(l,mid,node<<1);
	build(mid+1,r,node<<1|1);
	pushup(node);
}
void pushdown(ll l,ll r,ll node){
	ll k=t[node].lazy,mid=(l+r)>>1;
	if(k==0) return;
	t[node<<1].val+=k*(mid-l+1);
	t[node<<1].lazy+=k;
	t[node<<1|1].val+=k*(r-mid);
	t[node<<1|1].lazy+=k;
	t[node].lazy=0;
}
void updata(ll x,ll y,ll l,ll r,ll node,ll k){
	if(x<=l&&r<=y){
		t[node].val+=k*(r-l+1);
		t[node].lazy+=k;
		return;
	}
	pushdown(l,r,node);
	ll mid=(l+r)>>1;
	if(x<=mid) updata(x,y,l,mid,node<<1,k);
	if(y>mid) updata(x,y,mid+1,r,node<<1|1,k);
	pushup(node);
}
ll query(ll x,ll y,ll l,ll r,ll node){
	ll ans=0;
	if(x<=l&&r<=y) return t[node].val;
	pushdown(l,r,node);
	ll mid=(l+r)>>1;
	if(x<=mid) ans+=query(x,y,l,mid,node<<1);
	if(y>mid) ans+=query(x,y,mid+1,r,node<<1|1);
	return ans;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		c[i]=a[i]-a[i-1];
	}
	build(1,n,1);
	while(m--){
		ll op,x,y,k,d;
		cin>>op;
		if(op==1){
			cin>>x>>y>>k>>d;
			ll e=k+(y-x)*d;
			if(x+1<=y) updata(x,x,1,n,1,k);
			updata(x+1,y,1,n,1,d);
			if(y+1<=n) updata(y+1,y+1,1,n,1,-e);
		}
		else{
			cin>>k;
			cout<<query(1,k,1,n,1)<<endl;
		}
	}	
	return 0;
}
2024/7/10 21:14
加载中...