树状数组,9pts只过第一个点,玄关
查看原帖
树状数组,9pts只过第一个点,玄关
942161
Tomle楼主2024/1/28 12:42

记录

#include <bits/stdc++.h>
using namespace std;
int n,m,t[100005],a[100005],b[100005],cf[100005],cf2[100005],pre1[100005],pre2[100005],opt,l,r,k,d,p;
int lowbit(int k){
	return k&-k;
}
void add(int x,int k){
	int y=x;
	for(;x<=n;x+=lowbit(x)){
		a[x]+=k;
		b[x]+=k*y;
	}
}
int ask(int x){
	int A=0,B=0,y=x;
	for(;x;x-=lowbit(x)){
		A+=a[x];
		B+=b[x];
	}
	return A*(y+1)-B;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		scanf("%lld",t+i);
		cf[i]=t[i]-t[i-1];
		cf2[i]=cf[i]-cf[i-1];
		pre1[i]=pre1[i-1]+cf2[i];
		pre2[i]=pre2[i-1]+cf2[i]*i;
		a[i]=pre1[i]-pre1[i-lowbit(i)];
		b[i]=pre2[i]-pre2[i-lowbit(i)];
	}
	for(int i=1;i<=m;i++){
		cin>>opt;
		if(opt==1){
			cin>>l>>r>>k>>d;
			add(l,k);
			add(l+1,d-k);
			add(r+1,-(k+(r-l)*d)-d);
		}else{
			cin>>p;
			cout<<ask(p)<<endl;
		}
	}
}
2024/1/28 12:42
加载中...