题解：P13976 数列分块入门 1

虽然这题是数列分块题，但是这题也可以用线段树的方案解决，可以发现是单点查询区间更新问题，所以需要懒标记，设 toAdd 表示懒标记，则我们每次在线段树上更新时候，就采用区间三分离的方法，当无贡献的时候就直接返回，当整体贡献的时候这个整体的懒标记都加上

c

，否则就在子树中递归，直到整体贡献为止，就实现了一个基本的区间加。

然后如何单点查询，我们单点二选一。如果已经拆分成最小的区间（点），直接返回这个点的懒标记即可。否则二选一：若在左子树内，即当前询问的

id

在左子树的右端点以内，则左子树产生贡献，继续递归并在递归结束以后加上这个点的懒标记，否则右子树产生贡献，同样递归右子树加上这个点的懒标记。其实每次询问一个点，就是某个叶子到根的点权和，而这个叶子就是代表区间

[id,id]

的。

这样一步步模拟实现即可，时间复杂度

O(n \log n)

的。

AC 代码：

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=500009;
const ll MOD=100000007;
ll n,x[N];
struct Segment{
	ll l,r;
	ll toAdd;
};
Segment tr[N*4];
void build(ll u,ll l,ll r){
	if(l==r){
		tr[u]=(Segment){l,r,x[l]};
		return;
	}
	ll mid=(l+r)/2;
	build(u*2,l,mid);
	build(u*2+1,mid+1,r);
	tr[u]=(Segment){l,r,0};
}
void add(ll u,ll l,ll r,ll delta){
	if(r<tr[u].l||tr[u].r<l) return;
	if(l<=tr[u].l&&tr[u].r<=r){
		tr[u].toAdd+=delta;
		return;
	}
	add(u*2,l,r,delta);
	add(u*2+1,l,r,delta);
}
ll value(ll u,ll id){
	if(tr[u].l==tr[u].r)
		return tr[u].toAdd;
	if(id<=tr[u*2].r)
		return tr[u].toAdd+value(u*2,id);
	else
		return tr[u].toAdd+value(u*2+1,id);
}
int main(){
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++) scanf("%lld",&x[i]); 
	build(1,1,n);
	for(ll i=1;i<=n;i++){
		ll op,l,r,c;
		scanf("%lld %lld %lld %lld",&op,&l,&r,&c);
		if(op==0) add(1,l,r,c);
		else printf("%lld\n",value(1,r));
	}
	return 0;
}

题解：P13976 数列分块入门 1

文章操作

相关推荐

评论

题解：P13976 数列分块入门 1