[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$$
(ecause i-2+j+1=i-1+j, herefore f_{i-2+j}+f_{i-1+j}=f_{i+j})
( herefore 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 imes A+1 imes B=f_0A+f_1B)
$ ecause f_0=f_1,f_2=f_1+f_0=f_1+f_1$
( herefore 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])
容易看出(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 imes sumf(n-1))或(Delta imes (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
",query(l,r,1));
}else{
scanf("%d %d %d",&l,&r,&d);
update_add(l,r,d,1);
}
}
}