CF466C

• 在本题中，我们用 $f_i$ 来表示第 $i$ 个斐波那契数（$f_1=f_2=1,f_i=f_{i-1}+f_{i-2}(i\ge 3)$）。
• 维护一个序列 $a$，长度为 $n$，有 $m$ 次操作：
  1. 1 l r：对于 $l\le i\le r$，将 $a_i$ 加上 $f_{i-l+1}$。
  2. 2 l r：求 $\displaystyle\left(\sum_{i=l}^ra_i\right)\bmod(10^9+9)$。
• $1\le n,m\le 3\times 10^5$，$1\le a_i\le 10^9$。

思路

这是两年前遗留下来的一个问题了，两年前曾尝试过以下这个解法，却没有调出来。

看到是区间加斐波那契数列的一段和，立刻想到了斐波那契数列的一个性质：

$$\sum_{i=1}^n f(i)=f(n+2)-1=s(n)$$

于是想到了线段树维护区间和 $sum$ 和一个延迟标记 $lazy$ 。

对区间 $[L,R]$ 进行操作一，目前处理到其一个子区间 $[l,r]$ 时，只需对该子区间的 $sum$ 加上 $s(r-L+1)-s(l-L)$ ，并且修改其延迟标记为 $l-L+1$ 即可。

此即为两年前的思路，喜提 WA。

时至今日，在我重新看这道题时，仍用了很长时间才发现了问题所在（我太菜了qaq）。

这里的问题就在于，一个区间的延迟标记可能还没有下放，就被一个新的修改操作给覆盖了。

所以考虑优化这个算法。

于是我用了 vector 存放所有的延迟标记，下放时将所有的延迟标记都下放。

显然，当操作足够多时，这样的空间复杂度是爆炸的。如此，只通过了7个点。

我又想到，最后一层的节点是无需存放延迟标记的，所以再进行了一次优化，最后一层的节点不再存放延迟标记。如此，多通过了一个点。代码如下

#include<bits/stdc++.h>
#define ll long long 
#define N 300010
#define mod 1000000009

using namespace std;

inline ll read() {
    ll w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int n,m;
ll f[N];

class SegmentTree{
  private:
    ll sum[N<<2];
    vector<int> lazy[N<<2];
    #define s(x) sum[x]
    #define l(x) lazy[x]
    #define sf(l,r) ((f[r+2]-f[l+1])%mod+mod)
    #define ls (p<<1)
    #define rs (ls|1)
    #define mid (l+r>>1)
    void update(int p) {
        (s(p)=s(ls)+s(rs))%=mod;
    }
    void spread(int p,int l,int r) {
        if(l(p).empty()) return ;
        for(int i=0;i<l(p).size();i++) {
            (s(ls)+=sf(l(p)[i],l(p)[i]+mid-l))%=mod,l(ls).push_back(l(p)[i]);
            (s(rs)+=sf(l(p)[i]+mid-l+1,l(p)[i]+r-l))%=mod,l(rs).push_back(l(p)[i]+mid-l+1);
        }
        l(p).clear();
        if(l==mid) l(ls).clear();
        if(mid+1==r) l(rs).clear();
    }
  public:
    void build(int p,int l,int r) {
        l(p).clear();
        if(l==r) {
            s(p)=read()%mod;
            return ;
        }
        build(ls,l,mid),build(rs,mid+1,r);
        update(p);
    }
    void modify(int p,int l,int r,int L,int R,int x) {
        if(l>R||r<L) return ;
        if(l>=L&&r<=R) {
            (s(p)+=sf(x+l-L,x+r-L))%=mod;
            l(p).push_back(x+l-L);
            return ;
        }
        spread(p,l,r);
        modify(ls,l,mid,L,R,x),modify(rs,mid+1,r,L,R,x);
        update(p);
    }
    ll ask(int p,int l,int r,int L,int R) {
        if(l>R||r<L) return 0;
        if(l>=L&&r<=R) return s(p);
        spread(p,l,r);
        return (ask(ls,l,mid,L,R)+ask(rs,mid+1,r,L,R))%mod;
    }
}SMT;

void init() {
    f[0]=0,f[1]=1;
    for(int i=2;i<=n+2;i++) (f[i]=f[i-1]+f[i-2])%=mod;
    SMT.build(1,1,n);
}
int main() {
    n=read(),m=read();
    init();
    for(int i=1;i<=m;i++) {
        int op=read(),l=read(),r=read();
        if(op==1) SMT.modify(1,1,n,l,r,1);
        else printf("%lld\n",SMT.ask(1,1,n,l,r));
    }
    system("pause");
    return 0;
} 

万策已尽，看了看洛谷上的题解。

发现题解有好多做法，基本上都是围绕着广义斐波那契数列的性质来维护的。

为何是广义斐波那契数列？因为一个斐波那契数列加一个斐波那契数列还是斐波那契数列。

于是去看了看一些广义斐波那契数列的性质。

看到这样一个性质。

斐波那契数列 $f(n)$ ，广义斐波那契数列 $F(n)=F(n-1)+F(n-2),F(1)=x,F(2)=y$ ，则有

$$F(n)=xf(n-2)+yf(n-1)$$

证明考虑用数学归纳法：

有

$$\begin{align} F(1)&=x\\F(2)&=y\\F(3)&=x+y\\F(4)&=x+2y \end{align}$$

对于 $F(3)$ ， $F(3)=x+y=xf(1)+yf(2)$

对于 $F(4)$ ， $F(4)=x+2y=xf(2)+yf(3)$

那么由定义， $F(5)=x\Big[f(1)+f(2)]\Big]+y\Big[f(2)+f(3)\Big]=xf(3)+yf(4)$ 。

由数学归纳法，结论成立。

此外，该广义斐波那契数列同样有着一开始的那个性质：

$$\sum_{i=1}^nF(i)=F(n+2)-F(2)$$

于是可以考虑用线段树维护数列的第一项和第二项以及区间和，操作一直接用第一项与第二项加上斐波那契数列的对应项，区间和再根据上面的性质来修改。下放标记时同样对左右子节点的第一项和第二项加上对应项，对应项可由上面的另一性质 $O(1)$ 求得。

如此，即可解决本题。

代码

#include<bits/stdc++.h>
#define ll long long 
#define N 300010
#define mod 1000000009

using namespace std;

inline ll read() {
    ll w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int n,m;
ll f[N];

ll sf(ll x,ll y,int len) {
    if(len==1) return x;
    return ((x*f[len]%mod+y*f[len+1]%mod-y)%mod+mod)%mod;
}

class SegmentTree{
  private:
    ll sum[N<<2],lazy_first[N<<2],lazy_second[N<<2];
    #define s(x) sum[x]
    #define lt(x) lazy_first[x]
    #define ld(x) lazy_second[x]
    #define ls (p<<1)
    #define rs (ls|1)
    #define mid (l+r>>1)
    void update(int p) {
        (s(p)=s(ls)+s(rs))%=mod;
    }
    void spread(int p,int l,int r) {
        if(!lt(p)&&!ld(p)) return ;
        (lt(ls)+=lt(p))%=mod,(ld(ls)+=ld(p))%=mod;
        (s(ls)+=sf(lt(p),ld(p),mid-l+1))%=mod;
        ll x=lt(p)*f[mid-l]%mod+ld(p)*f[mid-l+1]%mod,y=lt(p)*f[mid-l+1]%mod+ld(p)*f[mid-l+2]%mod;
        (lt(rs)+=x)%=mod,(ld(rs)+=y)%=mod;
        (s(rs)+=sf(x,y,r-mid));
        lt(p)=ld(p)=0;
    }
  public:
    void build(int p,int l,int r) {
        lt(p)=ld(p)=0;
        if(l==r) {
            s(p)=read()%mod;
            return ;
        }
        build(ls,l,mid),build(rs,mid+1,r);
        update(p);
    }
    void modify(int p,int l,int r,int L,int R) {
        if(l>R||r<L) return ;
        if(l>=L&&r<=R) {
            (s(p)+=sf(f[l-L+1],f[l-L+2],r-l+1))%=mod;
            (lt(p)+=f[l-L+1])%=mod,(ld(p)+=f[l-L+2])%=mod;
            return ;
        }
        spread(p,l,r);
        modify(ls,l,mid,L,R),modify(rs,mid+1,r,L,R);
        update(p);
    }
    ll ask(int p,int l,int r,int L,int R) {
        if(l>R||r<L) return 0;
        if(l>=L&&r<=R) return s(p);
        spread(p,l,r);
        return (ask(ls,l,mid,L,R)+ask(rs,mid+1,r,L,R))%mod;
    }
}SMT;

void init() {
    f[0]=0,f[1]=1;
    for(int i=2;i<=n+2;i++) (f[i]=f[i-1]+f[i-2])%=mod;
    SMT.build(1,1,n);
}
int main() {
    n=read(),m=read();
    init();
    for(int i=1;i<=m;i++) {
        int op=read(),l=read(),r=read();
        if(op==1) SMT.modify(1,1,n,l,r);
        else printf("%lld\n",SMT.ask(1,1,n,l,r));
    }
    system("pause");
    return 0;
}