wa 9pts 玄关求助 仅AC #1
查看原帖
wa 9pts 玄关求助 仅AC #1
519276
W_Sibo楼主2024/10/14 19:02
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
struct tree{
	ll l,r,val,tag;
}tr[4*N];
ll n,m,a[N];
void build(int p,int l,int r){
	tr[p].l=l;
	tr[p].r=r;
	if(l==r){
		tr[p].val=a[l]-a[l-1];
		return;
	}
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
}
void pushdown(int p){
	tr[p*2].val+=(tr[p*2].r-tr[p*2].l+1)*tr[p].tag;
	tr[p*2+1].val+=(tr[p*2+1].r-tr[p*2+1].l+1)*tr[p].tag;
	tr[p*2].tag+=tr[p].tag;
	tr[p*2+1].tag+=tr[p].tag;
	tr[p].tag=0;
}
void update(int p,int l,int r,ll v){
	if(r<tr[p].l||tr[p].r<l) return;
	if(l<=tr[p].l&&tr[p].r<=r){
		tr[p].val+=(tr[p].r-tr[p].l+1)*v;
		tr[p].tag+=v;
		return;
	}
	pushdown(p);
	int mid=(l+r)>>1;
	update(p*2,l,r,v);
	update(p*2+1,l,r,v);
	tr[p].val=tr[p*2].val+tr[p*2+1].val; 
}
ll query(int p,int l,int r){
	if(r<tr[p].l||tr[p].r<l) return 0;
	if(l<=tr[p].l&&tr[p].r<=r) return tr[p].val;
	pushdown(p);
	int mid=(l+r)>>1;
	ll res=0;
	res+=query(p*2,l,r);
	res+=query(p*2+1,l,r);
	return res;
}
signed main(){
	//freopen("P1438_2.in","r",stdin);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int x;
		cin>>x;
		switch(x){
			case 1:{
				ll l,r,k,d;
				cin>>l>>r>>k>>d;
				update(1,l,l,k);
				if(l+1<=r) update(1,l+1,r,d);
				if(r<n) update(1,r+1,r+1,(l-r)*d-k);
				break;
			}case 2:{
				int p;
				cin>>p;
				cout<<query(1,1,p)<<'\n';
				break;
			}
		}
	}
}
2024/10/14 19:02
加载中...