[Codeforces 316E3]Summer Homework(线段树+斐波那契数列)
顺便安利一下这个博客,给了我很大启发()
题面
有一个数列\(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#include #include #define maxn 200000#define mod 1000000000using 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); } }}