线段树re四个求指点
查看原帖
线段树re四个求指点
431289
lalaouye楼主2022/7/15 13:24
#include<bits/stdc++.h>
using namespace std;

int a[1000001],n,m;int L,R,ans,diff[1000001];
struct tree{
	long long l,r,dat,add;
}tree[30000001];
void build(int p,int l,int r){
	tree[p].l=l;
	tree[p].r=r;
	if(l==r){
		tree[p].dat=diff[l];
		return;
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	tree[p].dat+=tree[p*2].dat+tree[p*2+1].dat;
}
void spread(int p){
	if(tree[p].add){
		tree[p*2].dat+=tree[p].add*(tree[p*2].r-tree[p*2].l+1);
		tree[p*2+1].dat+=tree[p].add*(tree[p*2+1].r-tree[p*2+1].l+1);
		tree[p*2].add+=tree[p].add;
		tree[p*2+1].add+=tree[p].add;
		tree[p].add=0;
	}
}
void change(int p,int l,int r,int d){
	if(l<=tree[p].l&&r>=tree[p].r){
		tree[p].dat+=d*(tree[p].r-tree[p].l+1);
		tree[p].add+=d;
		return;
	}
	spread(p);
	int mid=(tree[p].l+tree[p].r)/2;
	if(l<=mid) change(p*2,l,r,d);
	if(r>mid) change(p*2+1,l,r,d);
	tree[p].dat=tree[p*2+1].dat+tree[p*2].dat;
}
long long ask(int p,int l,int r){
	long long ans=0;
	if(l<=tree[p].l&&r>=tree[p].r){
		return tree[p].dat;
	}
	spread(p);
	int mid=(tree[p].l+tree[p].r)/2;
	if(l<=mid) ans+=ask(p*2,l,r);
	if(r>mid) ans+=ask(p*2+1,l,r);
	return ans;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		diff[i]=a[i]-a[i-1];
	}
	build(1,1,n);
	while(m--){
		int o,b,p,k,l;
		scanf("%d",&o);
		if(o==1){
			scanf("%d%d%d%d",&p,&b,&k,&l);
			change(1,p,p,k);
			change(1,p+1,b,l);
			change(1,b+1,b+1,-(b-p)*l-k);
			//cout<<-(b-p)*l-k<<" ";
		}else{
			scanf("%d",&p);
			printf("%lld\n",ask(1,1,p));
		}
	}
} 
2022/7/15 13:24
加载中...