[Codeforces 316E3]Summer Homework(线段树+斐波那契数列)

顺便安利一下这个博客,给了我很大启发(https://gaisaiyuno.github.io/)

题面

有一个数列$f_i$满足$f_0=f_1=1,f_i=f_{i-1}+f_{i-2}(i>2)$(就是斐波那契数列)

给定一个n个数的数列a,m个操作，有3种操作

1.将$a_x$的值修改成v (单点修改)

2.对于$i \in [l,r],a_i+=v$ (区间修改)

3.求$\sum_{i=l}^r x_if_{i-l}$

分析

显然是用线段树，考虑如何合并区间

定义$s_0=f_0a_0+f_1a_1+...+f_na_n$,$s_1=f_1a_0+f_2a_1+...+f_{n+1}a_n$

即$$s_i=\sum_{j=0}^n f_{j+i}a_j$$

那么$$s_{i-2}+s_{i-1}= \sum_{j=0}^n f_{i-2+j}a_j+\sum_{j=0}^n f_{i-1+j}a_j= \sum_{j=0}^n (f_{i-2+j}+f_{i-1+j}) a_j$$

$\because i-2+j+1=i-1+j,\ \therefore f_{i-2+j}+f_{i-1+j}=f_{i+j}$

$\therefore s_{i-2}+s_{i-1}=\sum_{j=0}^n (f_{i-2+j}+f_{i-1+j}) a_j=\sum_{j=0}^n f_{i+j} a_j=s_i$

于是我们得到了非常重要的一个性质$$ s_i=s_{i-1}+s_{i-2} $$

直接在线段树上记录s肯定是不行的，现在我们想办法用$s_0$和$s_1$推出任意$s_n$

不妨设$s_0=A,s_1=B$,发现$s_2=s_0+s_1=1\times A+1\times B=f_0A+f_1B$

$ \because f_0=f_1,f_2=f_1+f_0=f_1+f_1$

$\therefore s_3=s_1+s_2=f_1B+f_0A+f_1B=f_1A+f_2B$

$s_4=s_2+s_3=(f_0+f_1)A+(f_1+f_2)B=f_2A+f_3B$

$s_5=s_3+s_4=(f_1+f_2)A+(f_2+f_3)B=f_3A+f_4B$

$\dots$

根据数学归纳法，$$s_i=f_{i-2}s_0+f_{i-1}s_1$$

那么，如何把这几个结论运用到线段树上呢？

(1)pushup:

我们考虑合并线段树节点x的两个子节点lx,rx,得到x的s0,s1值,设子节点的区间为$[l,md],[md+1,r]$

\[s_0(x)=\sum_{i=0}^{r-l} f_is_i=\sum_{i=0}^{md-l} f_is_i+\sum_{i=md+1-l}^{r-l}f_is_i
\]

容易看出$\sum_{i=0}^{md} f_is_i=s_0(lx)，\sum_{i=md+1-l}^{r-l}f_is_i=\sum_{j=0}^{r-md-1} f_{j+(md-l+1)}a_j=s_{md-l+1}(rx)=s_{len(lx)}(rx)$，其中len(k)表示k节点对应的区间长度,其实就是相当于把右区间的s值偏移了左区间长度那么多

所以有$s_0(x)=s_0(lx)+s_{len(lx)}(rx)$，同理有$s_1(x)=s_1(lx)+s_{len(lx)+1}(rx)$

(2)push_down

考虑区间加法对答案的贡献，假设加上的数为$\Delta$

$s_0'=f_0(a_0+\Delta)+f_1(a_1+\Delta)+\dots+f_n(a_{n-1}+\Delta)=s_0+\Delta(f_0+f_1+\dots f_{n-1})$ (这里的n为区间长度，由于从0开始需要-1)

同理$s_1'=s_0+\Delta(f_1+f_2+\dots f_{n})$

因此我们只需要预处理f的前缀和sumf，这样只用加上$\Delta \times sumf(n-1)$或$\Delta \times (sumf(n)-sumf(0))$

代码

//https://blog.csdn.net/y752742355/article/details/80449062

#include<iostream>

#include<cstdio>

#include<cstring>

#define maxn 200000

#define mod 1000000000

using namespace std;

int n,m;

long long a[maxn+5];

long long f[maxn+5];

long long sumf[maxn+5];

void ini(){

	f[0]=f[1]=1;

	for(int i=2;i<=maxn;i++){

		f[i]=(f[i-1]+f[i-2])%mod;

	}

	sumf[0]=1;

	for(int i=1;i<=maxn;i++){

		sumf[i]=(sumf[i-1]+f[i])%mod;

	}

}

struct node{

	int l;

	int r;

	long long s0;

	long long s1;

	int mark;

	int len(){

		return r-l+1;

	}

}tree[maxn*4+5];

inline long long fib(int n){//防止越界

	return n<0?0:f[n];

}

inline long long get_s(int pos,int n){//返回s_n(pos)

	return tree[pos].s0*fib(n-2)+tree[pos].s1*fib(n-1);

}

void push_up(int pos){

	tree[pos].s0=(tree[pos<<1].s0+get_s(pos<<1|1,tree[pos<<1].len()))%mod;

	tree[pos].s1=(tree[pos<<1].s1+get_s(pos<<1|1,tree[pos<<1].len()+1))%mod;

}

void build(int l,int r,int pos){

	tree[pos].l=l;

	tree[pos].r=r;

	if(l==r){

		tree[pos].s0=a[l]%mod;

		tree[pos].s1=a[l]%mod;

		return;

	}

	int mid=(l+r)>>1;

	build(l,mid,pos<<1);

	build(mid+1,r,pos<<1|1);

	push_up(pos);

}

void push_down(int pos){

	if(tree[pos].mark){

		tree[pos<<1].mark=(tree[pos<<1].mark+tree[pos].mark)%mod;

		tree[pos<<1|1].mark=(tree[pos<<1|1].mark+tree[pos].mark)%mod;

		tree[pos<<1].s0=(tree[pos<<1].s0+sumf[tree[pos<<1].len()-1]*tree[pos].mark%mod)%mod;

		tree[pos<<1].s1=(tree[pos<<1].s1+(sumf[tree[pos<<1].len()]-sumf[0])*tree[pos].mark%mod)%mod;

		tree[pos<<1|1].s0=(tree[pos<<1|1].s0+sumf[tree[pos<<1|1].len()-1]*tree[pos].mark%mod)%mod;

		tree[pos<<1|1].s1=(tree[pos<<1|1].s1+(sumf[tree[pos<<1|1].len()]-sumf[0])*tree[pos].mark%mod)%mod;

		tree[pos].mark=0;

	}

}

void update_add(int L,int R,long long v,int pos){

	if(L<=tree[pos].l&&R>=tree[pos].r){

		tree[pos].mark=(tree[pos].mark+v)%mod;

		tree[pos].s0=(tree[pos].s0+sumf[tree[pos].len()-1]*v%mod)%mod;

		tree[pos].s1=(tree[pos].s1+(sumf[tree[pos].len()]-sumf[0])*v%mod)%mod;

		return;

	}

	push_down(pos);

	int mid=(tree[pos].l+tree[pos].r)>>1;

	if(L<=mid) update_add(L,R,v,pos<<1);

	if(R>mid) update_add(L,R,v,pos<<1|1);

	push_up(pos);

}

void update_set(int upos,long long v,int pos){

	if(tree[pos].l==tree[pos].r){

		tree[pos].s0=v%mod;

		tree[pos].s1=v%mod;

		tree[pos].mark=0;

		return;

	}

	push_down(pos);

	int mid=(tree[pos].l+tree[pos].r)>>1;

	if(upos<=mid) update_set(upos,v,pos<<1);

	else update_set(upos,v,pos<<1|1);

	push_up(pos);

}

long long query(int L,int R,int pos){

	if(L<=tree[pos].l&&R>=tree[pos].r){

		int len=tree[pos].l-L;//注意合并答案时也要加上偏移值，和push_up一个原理

		if(len==0) return tree[pos].s0;

		else return get_s(pos,len);

	}

	push_down(pos);

	int mid=(tree[pos].l+tree[pos].r)>>1;

	long long ans=0;

	if(L<=mid) ans=(ans+query(L,R,pos<<1))%mod;

	if(R>mid) ans=(ans+query(L,R,pos<<1|1))%mod;

	return ans;

} 

int main(){

	int opt,x,v,l,r,d;

	scanf("%d %d",&n,&m);

	ini();

	for(int i=1;i<=n;i++){

		scanf("%I64d",&a[i]);

	}

	build(1,n,1);

	for(int i=1;i<=m;i++){

		scanf("%d",&opt);

		if(opt==1){

			scanf("%d %d",&x,&v);

			update_set(x,v,1);

		}else if(opt==2){

			scanf("%d %d",&l,&r);

			printf("%I64d\n",query(l,r,1));

		}else{

			scanf("%d %d %d",&l,&r,&d);

			update_add(l,r,d,1);

		}

	}

}

秒客网

[Codeforces 316E3]Summer Homework(线段树+斐波那契数列)

[Codeforces 316E3]Summer Homework(线段树+斐波那契数列)

题面

分析

代码

相关文章