CF316 E3. Summer Homework

设 $F$ 为斐波那契数列，不妨设 $F_{-1}=1$
整个数列也就是 $F_{-1}=1,F_{0}=0,F_{1}=1,F_{2}=1,F_{3}=2,F_{4}=3,F_{5}=5,F_{6}=8,....$

定义数列 $S(0)=F_1a_1+F_2a_2+F_3a_3+...+F_na_n$ ，
定义数列 $S(1)=F_2a_1+F_3a_2+F_4a_3+...+F_{n+1}a_n$
即：

S(m)=\sum_{i=1}^{i \le n} F_{i+m}a_i

发现：
$S(m+1)+S(m+2)=\sum_{i=1}^{i \le n} F_{i+m+1}a_i + \sum_{i=1}^{i \le n} F_{i+m+2}a_i=\sum_{i=1}^{i \le n} F_{i+m+3}a_i$
$=S(m+3)$

所以， $S$ 数列的递推关系的类似于斐波那契数列的递推关系。

现在，我们想只用 $S(0)$ 和 $S(1)$ 推出任意 $S(m)$
不妨设 $S(0)=A$ ， $S(1)=B$ ，发现

S(0)=A \times F_{-1}+B \times F_0

S(1)=A \times F_0 + B \times F_1

S(2)=A \times F_1 + B \times F_2

S(3)=A \times F_2 + B \times F_3

S(4)=A \times F_3 + B \times F_4

....

最后我们发现： $S(m)=F_{m-1} \times A+F_{m} \times B = F_{m-1} \times S(0)+F_{m} \times S(1)$ ，且 $S(0)，S(1)$ 是特殊情况需要加特判

考虑如何修改 $S(0)$ 和 $S(1)$ ，假设加上的数为c，发现：

S'(0)=F_1(a_1+c)+F_2(a_2+c)+F_3(a_3+c)+...+F_n(a_n+c)

=F_1a_1+F_2a_2+F_3a_3+...+F_na_n+c \times (F_1+F_2+F_3+...+F_n)

=S(0)+c \times (F_1+F_2+F_3+...+F_n)

所以，我们只要预处理 $F$ 数组前缀和即可，修改 $S(1)$ 也是同理。

考虑如何维护信息：
设当前要合并的两个区间分别为 $[l_1,r_1][l_2,r_2]$
发现 $S(0)=\sum_{i=l_1}^{i \le r_2} F_{i}a_i$
$=\sum_{i=l_1}^{i \le r_1}F_ia_i + \sum_{i=l_2+1}^{i \le r_2}F_ia_i$
$=S_l(0)+S_r(l_1-r_1+1)$
维护 $S(1)$ 也是同理。

记得要开 $\rm long$ $\rm long$ 并且疯狂取模。

具体要看代码（可能和思路在下标上有所不同）

#include <bits/stdc++.h>
#define MOD 1000000000
#define MAXN 200005
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int a[MAXN],f[MAXN],pref[MAXN],pref2[MAXN];
inline void Init(){//预处理F数组和前缀和
    f[1]=1,f[2]=2;
    for (register int i=3;i<MAXN;++i){
        f[i]=(f[i-1]+f[i-2])%MOD;
    }
    for (register int i=1;i<MAXN;++i){
        pref2[i]=(pref2[i-1]+f[i])%MOD;
    }
 
    f[1]=1,f[2]=1;
    for (register int i=3;i<MAXN;++i){
        f[i]=(f[i-1]+f[i-2])%MOD;
    }
    for (register int i=1;i<MAXN;++i){
        pref[i]=(pref[i-1]+f[i])%MOD;
    }
}
namespace SegmentTree{
    struct node{
        int l,r;
        int s0,s1;
        int tag;
        inline int len(){return r-l+1;}
    }tree[MAXN<<2];
    inline int Get_S(int x,int n){//求S(m)
        if (n==1) return tree[x].s0;
        if (n==2) return tree[x].s1;
        return (tree[x].s0*f[n-2]%MOD+tree[x].s1*f[n-1]%MOD)%MOD;
    }
    #define lc i<<1
    #define rc i<<1|1
    inline void pushup(int i){
        tree[i].s0=(tree[lc].s0+Get_S(rc,tree[lc].len()+1))%MOD;
        tree[i].s1=(tree[lc].s1+Get_S(rc,tree[lc].len()+2))%MOD;
    }
    inline void Change(int i,int c){
        int l=tree[i].len();
        tree[i].s0=(tree[i].s0+pref[l]*c%MOD)%MOD;
        tree[i].s1=(tree[i].s1+pref2[l]*c%MOD)%MOD;
    }
    inline void pushdown(int i){
        if (tree[i].tag){
            Change(lc,tree[i].tag);
            Change(rc,tree[i].tag);
            tree[lc].tag=(tree[lc].tag+tree[i].tag)%MOD;
            tree[rc].tag=(tree[rc].tag+tree[i].tag)%MOD;
            tree[i].tag=0;
        }
    }
    void Build(int i,int l,int r){
        tree[i].l=l,tree[i].r=r;
        tree[i].tag=0;
        if (l==r){
            tree[i].s0=tree[i].s1=a[l];
            return ;
        }
        int mid=(l+r)>>1;
        Build(lc,l,mid);
        Build(rc,mid+1,r);
        pushup(i);
    }
    void Update(int i,int L,int R,int val){
        if (L<=tree[i].l&&tree[i].r<=R){
            tree[i].tag=(tree[i].tag+val)%MOD;
            Change(i,val);
            return ;
        }
        pushdown(i);
        int mid=(tree[i].l+tree[i].r)>>1;
        if (L<=mid) Update(lc,L,R,val);
        if (mid<R) Update(rc,L,R,val);
        pushup(i);
    }
    void Update_Pos(int i,int index,int val){
        if (tree[i].l==tree[i].r){
            tree[i].s1=tree[i].s0=val;
            return ;
        }
        pushdown(i);
        int mid=(tree[i].l+tree[i].r)>>1;
        if (index<=mid) Update_Pos(lc,index,val);
        else Update_Pos(rc,index,val);
        pushup(i);
    }
    int Query(int i,int L,int R){
        if (L<=tree[i].l&&tree[i].r<=R){
            return Get_S(i,tree[i].l-L+1);
        }
        pushdown(i);
        int mid=(tree[i].l+tree[i].r)>>1;
        int ans=0;
        if (L<=mid) ans=(ans+Query(lc,L,R))%MOD;
        if (mid<R) ans=(ans+Query(rc,L,R))%MOD;
        return ans;
    }
}
using namespace SegmentTree;
#undef int
int main(){
#define int long long
    Init();
    int n=read(),m=read();
    for (register int i=1;i<=n;++i){
        a[i]=read();
    }
    Build(1,1,n);
    for (register int i=1;i<=m;++i){
        int opr=read();
        if (opr==1){
            int pos=read(),x=read();
            Update_Pos(1,pos,x);
        }
        else if (opr==2){
            int l=read(),r=read();
            printf("%I64d\n",Query(1,l,r));
        }
        else if (opr==3){
            int l=read(),r=read(),val=read();
            Update(1,l,r,val);
        }
    }
}