首页 > 代码库 > Codeforces 446C 线段树 递推Fibonacci公式
Codeforces 446C 线段树 递推Fibonacci公式
聪哥推荐的题目
区间修改和区间查询，但是此题新颖之处就在于他的区间修改不是个定值，而是从L 到 R 分别加 F1、F2、。。。Fr-l+1 （F为斐波那契数列）
想了一下之后，觉得用fib的前缀和来解决，每次做懒惰标记记录下当前区间是从哪个L开始加起的，敲了一半之后发现有问题，就跟上次遇到的懒惰标记问题一样，这是个覆盖性的懒惰标记，每次向下传递后，都要先清除孩子的，清除孩子的也有可能要清除son‘s son，所以要一直pushdown下去，否则就会错，但这样就会超时。
能不能有个累加型的标记让我不用pushdown呢，网上都用的什么二次剩余定理，实在不会
后来发现一个博客的做法相当精妙，利用了斐波那契的特性
我们知道 fib总是由两个两个往后推得 则
若当前 数列前两项 为 a 、b，则之后的必为 a+b a+2b 2a+3b 3a+5b
推完发现 只要知道前两项，后面的任意一项都可以马上出来，因为其系数也满足fib数列
令 K=1,0,1,1,2.。。Ki=Ki-1+Ki-2,。
再令 F=0,1,1,2,3.。。为普通fib数列
则知道 前两项为 a,b,可推算出任意一项 n=Kn*a+Gn*b；
同理，我们可以推算出来，知道前两项后，前n项的总和为
Fn*a+Sn*b（S为fib的前缀和）。
这样的话，我只要每次懒惰标记当前区间的前两项，向下传递就会马上得到区间的加值，并且传递给左右孩子的时候，能根据右孩子的区间不同，马上把前两项变为适合右孩子的那两项。。。最重要的是，这个前两项支持累加，也就是累加型懒惰标记，不用彻底向下传递，这真的是极好的
#include <iostream>#include <cstdio>#include <cstring>#define LL __int64#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,rconst LL M=1000000009;const int N=300000+20;LL F[N],K[N],G[N],A[N];int n,m;LL d[N<<2],f[N<<2],f1[N<<2],f2[N<<2];void init(){ F[0]=G[0]=0; K[0]=1; F[1]=1; G[1]=0; K[1]=0; for (int i=2;i<=n+10;i++){ F[i]=F[i-1]+F[i-2]; K[i]=K[i-1]+K[i-2]; G[i]=G[i-1]+F[i-1]; if (F[i]>=M) F[i]%=M; if (K[i]>=M) K[i]%=M; if (G[i]>=M) G[i]%=M; } for (int i=1;i<=n;i++) scanf("%d",&A[i]);}void up(int rt){ d[rt]=d[rt<<1]+d[rt<<1|1]; if (d[rt]>=M) d[rt]%=M;}void build(int rt,int l,int r){ f[rt]=0; if (l>=r){ d[rt]=A[l]%M; return; } int mid=(l+r)>>1; build(lson); build(rson); up(rt);}void fix(LL v1,LL v2,int L,int R,int rt,int l,int r);void pushdown(int rt,int l,int r){ if (l>=r) return; if (!f[rt]) return; int mid=(l+r)>>1; fix(f1[rt],f2[rt],l,mid,lson); LL t1=K[mid-l+1]*f1[rt]%M+K[mid-l+2]*f2[rt]%M; LL t2=K[mid-l+2]*f1[rt]%M+K[mid-l+3]*f2[rt]%M; if (t1>=M) t1%=M; if (t2>=M) t2%=M; fix(t1,t2,mid+1,r,rson); f[rt]=0;}void fix(LL v1,LL v2,int L,int R,int rt,int l,int r){ if (L==l && r==R){ //采用这种锁定区间的方法是因为下面有个地方要用L计算，我之前的那种写法会出错 d[rt]+=(v1*F[R-L+1]%M+G[R-L+1]*v2%M)%M; if (d[rt]>=M) d[rt]%=M; if (!f[rt]){ f1[rt]=v1%M; f2[rt]=v2%M; f[rt]=1; } else{ f1[rt]+=v1%M; f2[rt]+=v2%M; if (f1[rt]>=M) f1[rt]%=M; if (f2[rt]>=M) f2[rt]%=M; } return; } int mid=(l+r)>>1; pushdown(rt,l,r); if (R<=mid) fix(v1,v2,L,R,lson); else if (L>mid) fix(v1,v2,L,R,rson); else { fix(v1,v2,L,mid,lson); LL t1=K[mid-L+1]*v1%M+K[mid-L+2]*v2%M;//这里L要进行计算，每个孩子对应唯一L，所以为什么我要采用这种锁定区间的方式，就是因为这里。以前以为两种锁定区间的方法差不多，现在找到区别了，如果只是简单为了锁定区间，两种都可以用，但是当区间要作为计算条件的时候，要采取这种方法避免错误 LL t2=K[mid-L+2]*v1%M+K[mid-L+3]*v2%M; if (t1>=M) t1%=M; if (t2>=M) t2%=M; fix(t1,t2,mid+1,R,rson); } up(rt);}LL query(int L,int R,int rt,int l,int r){ if (L<=l && r<=R){ return d[rt]%M; } pushdown(rt,l,r); int mid=(l+r)>>1; LL ret1=0,ret2=0; if (L<=mid) ret1=query(L,R,lson); if (R>mid) ret2=query(L,R,rson); return (ret1+ret2)%M;}int main(){ int op,a,b; while (scanf("%d%d",&n,&m)!=EOF) { init(); build(1,1,n); while (m--) { scanf("%d%d%d",&op,&a,&b); if (op==1){ fix(1,1,a,b,1,1,n); } else{ LL ans=query(a,b,1,1,n); printf("%I64d\n",ans); } } } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。