题面

解题思路

线段树

题目中涉及了区间加、区间修改，因此定是线段树的题

但是明显，就算区间转移，但是由于斐波那契数列在累加，可能一个区间内的斐波那契数列的第一、二项的不会仅仅是普通斐波那契数列中的任意一样，也就是出现广义斐波那契数列的情况

设普通斐波那契数列为 $\large {F_n}$，广义斐波那契数列为 $\large {S_n}$

1、$\large \forall $ 任一广义斐波那契数列有：

证明：

$\large S_3=S_2+S_1$

$\large S_4=S_3+S_2=S_2+S_1+S_2$

$\large S_5=S_4+S_3=S_3+S_2+S_1+S_2$

$\large S_6=S_5+S_4=S_4+S_3+S_2+S_1+S_2$

$\large S_7=S_6+S_5=S_5+S_4+S_3+S_2+S_1+S_2$

$\large \dots$

移项可得：

$\large S_4-S_2=S_2+S_1$

$\large S_5-S_2=S_3+S_2+S_1$

$\large S_6-S_2=S_4+S_3+S_2+S_1$

$\large S_7-S_2=S_5+S_4+S_3+S_2+S_1$

$\large \dots$

2、$\large \forall$ 任一广义斐波那契数列，有

于是只要把这两个性质合理地运用一下，写成函数，就可以很快地进行求和和求任一一项的操作，这将在 $push$ 函数里大有用处

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define inf 0x7f7f7f7f

#define p 1000000009
#define N 300007
using namespace std;
int n,T,L,R,tl[N<<2],tr[N<<2];
int f[N<<2],sum[N],fib[N];
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
inline int dec(rint x) {return (x>=p)?x-p:x;}
inline int rec(rint x) {return (x<0)?x+p:x;}//这两个都是取模函数
inline int calc(rint k,rint l,rint r) {return (k>1)?(1ll*fib[k-2]*l+1ll*fib[k-1]*r)%p:l;}//求第k项
inline int Sum(rint k,rint l,rint r) {return rec((1ll*l*fib[k]+1ll*r*fib[k+1])%p-r);}//前k项和
inline void push(rint k,rint l,rint r) {//下传标记
    f[k]=dec(f[k]+Sum(r-l+1,tl[k],tr[k]));
    if(l!=r) {
        rint mid=(l+r)>>1,ls=k<<1;
        tl[ls]=dec(tl[ls]+tl[k]),tl[ls|1]=dec(tl[ls|1]+calc(mid-l+2,tl[k],tr[k])),
        tr[ls]=dec(tr[ls]+tr[k]),tr[ls|1]=dec(tr[ls|1]+calc(mid-l+3,tl[k],tr[k]));
    }tl[k]=tr[k]=0;
}
inline void Modify(rint k,rint l,rint r) {
    if(tl[k]||tr[k]) push(k,l,r);
    if(r<L||R<l) return;
    if(L<=l&&r<=R) {tl[k]=fib[l-L+1],tr[k]=fib[l-L+2];return push(k,l,r);}
    rint mid=(l+r)>>1,ls=k<<1;
    Modify(ls,l,mid),Modify(ls|1,mid+1,r);
    f[k]=dec(f[ls]+f[ls|1]);
}
inline int Query(rint k,rint l,rint r) {
    if(tl[k]||tr[k]) push(k,l,r);
    if(r<L||R<l) return 0;
    if(L<=l&&r<=R) return f[k];
    rint mid=(l+r)>>1,ls=k<<1;
    return dec(Query(ls,l,mid)+Query(ls|1,mid+1,r));
}
int main()
{
    int i,op;
    n=read(),T=read();
    for(i=1;i<=n;i++) sum[i]=dec(sum[i-1]+read());
    fib[1]=fib[2]=1;
    for(i=1;i<=n+2;++i) fib[i+2]=dec(fib[i]+fib[i+1]);//预处理出Fib数列
    while(T--) {
        op=read(),L=read(),R=read();
        (op<2)?Modify(1,1,n),1:printf("%d\n",dec(Query(1,1,n)+rec(sum[R]-sum[L-1])));
    }
    return 0;
}

devil.