pts 91 #4wa 求助
查看原帖
pts 91 #4wa 求助
764396
telgs楼主2023/7/14 17:21
#include<iostream>
using namespace std;
const int N=2e5+10;
typedef long long ll;
ll n,m;
ll a[N];
struct Node{
	ll l,r;
	ll sum,add;
}tr[N*4];
void pushup(int u){
	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void pushdown(int u){
	tr[u<<1].add+=tr[u].add,tr[u<<1|1].add+=tr[u].add; 
	tr[u<<1].sum+=(tr[u<<1].r-tr[u<<1].l+1)*tr[u].add,tr[u<<1|1].sum+=(tr[u<<1|1].r-tr[u<<1|1].l+1)*tr[u].add;
	tr[u].add=0; 
} 
void build(int u,ll l,ll r){
	tr[u]={l,r};
	if(l==r){
		tr[u]={l,r,a[l]-a[l-1],0};
		return;
	}
	ll mid=l+r>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
	pushup(u);
} 
void modify(int u,ll l,ll r,ll add){
	if(tr[u].l>=l&&tr[u].r<=r){
		tr[u].add+=add;
		tr[u].sum+=(tr[u].r-tr[u].l+1)*add;
	}else{
		pushdown(u);
		ll mid=tr[u].l+tr[u].r>>1;
		if(l<=mid) modify(u<<1,l,r,add);
		if(r>mid) modify(u<<1|1,l,r,add);
		pushup(u);
	}
}
ll query(int u,ll l,ll r){
	if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;
	else{
		pushdown(u);
		ll mid=tr[u].l+tr[u].r>>1;
		ll sum=0;
		if(l<=mid) sum+=query(u<<1,l,r);
		if(r>mid) sum+=query(u<<1|1,l,r);
		return sum; 
	} 
}
int main(){
	scanf("%lld %lld",&n,&m);
	ll q,l,r,op,p;
	ll k,d;
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	build(1,1,n);
	for(int i=1;i<=m;i++){
		scanf("%lld",&op); 
		if(op==1){
			scanf("%lld %lld %lld %lld",&l,&r,&k,&d);
			ll sum=k+(r-l)*d;
			modify(1,l,l,k),modify(1,l+1,r,d);
			if(r+1<=n) modify(1,r+1,r+1,-sum);
		}else{
			scanf("%lld",&p);
			ll ans=query(1,1,p);
			printf("%lld\n",ans);
		}
	}
	return 0;
}
2023/7/14 17:21
加载中...