题目概述

有两种操作：1.将 $a_i,i\in[L,R]$ 加上 $fib_{i-L+1}$ 。2.求 $\sum_{i=L}^{R}a_i$ 。

解题报告

水Blog.jpg。先把原序列改成 $0​$（询问的时候再加上），由于斐波那契数列只需要知道前两项就可以得到后面，而且前两项是可以叠加的，所以我们就可以用线段树轻松维护，然后用矩阵快速幂快速得到某一项。

示例程序

#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;
const int maxn=300000,MOD=1e9+9;

int n,m,A[maxn+5],l[(maxn<<2)+5],r[(maxn<<2)+5],sum[(maxn<<2)+5];
struct Matrix{
    int r,c,s[2][2];
    inline void zero(int n,int m) {r=n;c=m;for (int i=0;i<r;i++) for (int j=0;j<c;j++) s[i][j]=0;}
    inline void unit(int n) {zero(n,n);for (int i=0;i<n;i++) s[i][i]=1;}
};
Matrix T,fst,now,s[maxn+5],pre[maxn+5],tag[(maxn<<2)+5],c;
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline Matrix operator + (const Matrix &a,const Matrix &b){
    c.zero(a.r,a.c);
    for (int i=0;i<c.r;i++)
        for (int j=0;j<c.c;j++)
            AMOD(c.s[i][j]=a.s[i][j],b.s[i][j]);
    return c;
}
inline Matrix operator * (const Matrix &a,const Matrix &b){
    c.zero(a.r,b.c);
    for (int i=0;i<c.r;i++)
        for (int j=0;j<c.c;j++)
            for (int k=0;k<a.c;k++)
                AMOD(c.s[i][j],(LL)a.s[i][k]*b.s[k][j]%MOD);
    return c;
}

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=0,f=1;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    if (lst=='-') f=-f;
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return x=tot*f,Eoln(ch);
}
#define LS (p<<1)
#define RS (p<<1|1)
void Build(int L,int R,int p=1){
    l[p]=L;r[p]=R;tag[p].zero(1,2);if (L==R) return;
    int mid=L+(R-L>>1);Build(L,mid,LS);Build(mid+1,R,RS);
}
#define val(S,p) (((S)*pre[r[p]-l[p]]).s[0][1])
#define Pushup(p) AMOD(sum[p]=sum[LS],sum[RS])
inline void Pushdown(int p){
    if (!tag[p].s[0][0]&&!tag[p].s[0][1]) return;
    static Matrix now;now=tag[p];tag[p].zero(1,2);
    AMOD(sum[LS],val(now,LS));tag[LS]=tag[LS]+now;now=now*s[l[RS]-l[p]];
    AMOD(sum[RS],val(now,RS));tag[RS]=tag[RS]+now;
}
void Insert(int L,int R,int p=1){
    if (R<l[p]||r[p]<L) return;
    if (L<=l[p]&&r[p]<=R) {now=fst*s[l[p]-L];AMOD(sum[p],val(now,p));tag[p]=tag[p]+now;return;}
    Pushdown(p);int mid=l[p]+(r[p]-l[p]>>1);Insert(L,R,LS);Insert(L,R,RS);Pushup(p);
}
int Ask(int L,int R,int p=1){
    if (R<l[p]||r[p]<L) return 0;if (L<=l[p]&&r[p]<=R) return sum[p];
    Pushdown(p);int mid=l[p]+(r[p]-l[p]>>1),ans;AMOD(ans=Ask(L,R,LS),Ask(L,R,RS));return ans;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);readi(m);for (int i=1,x;i<=n;i++) readi(x),AMOD(A[i]=A[i-1],x%MOD);
    T.zero(2,2);T.s[0][1]=T.s[1][0]=T.s[1][1]=1;s[0].unit(2);pre[0]=s[0];
    for (int i=1;i<=n;i++) s[i]=s[i-1]*T;for (int i=1;i<=n;i++) pre[i]=pre[i-1]+s[i];
    fst.zero(1,2);fst.s[0][1]=1;Build(1,n);
    for (int td,L,R,ans;m;m--){
        readi(td);readi(L);readi(R);
        if (td==1) Insert(L,R);
        else AMOD(ans=Ask(L,R),A[R]),AMOD(ans,MOD-A[L-1]),printf("%d\n",ans);
    }
    return 0;
}