CF446C DZY Loves Fibonacci Numbers

题目大意

• 在本题中，我们用 \(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\)。

分析

首先看到区间查询，区间修改，考虑用线段树。

但是，我们看到区间修改这个操作，如果真的去暴力写，则时间一定T，因为没办法加懒标记，每次加的都不同。

我们是要求和，这里有两个性质。

设a数组符合Fibonacci数列的递推式，其中\(a_1,a_2\)为任意值

其有\(a_i=f_{i-1}*a_2+f{i-2}*a_1\)，以及\(\sum_{i=1}^{n}a_i=f_n*a_1+(f_{n+1}-1)*a_2\)

依据这两个性质，我们直接维护两个懒标记f1，f2。其分别表示，该区间的待下传的f_1，f_2是多少。

Ac_code

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using namespace std;
typedef long long LL;

const int N = 3e5 + 10,mod = 1e9 + 9;

struct Node
{
    int l,r;
    LL v,f1,f2;
}tr[N<<2];

int n,m;
LL f[N],a[N];

void pushup(int u)
{
    tr[u].v = (tr[u<<1].v + tr[u<<1|1].v)%mod;
}

void build(int u,int l,int r)
{
    if(l==r)
    {
        tr[u] = {l,r,a[l]};
        return ;
    }
    tr[u] = {l,r};
    int mid = l + r >> 1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    pushup(u);
}

void change(Node &u,int l,int r,LL f1,LL f2)
{
    u.f1 += f1;u.f1 %= mod;
    u.f2 += f2;u.f2 %= mod;
    u.v += f2*(f[r-l+2]-1) + f1*f[r-l+1];u.v %= mod;
}

void pushdown(int k)
{
    if(tr[k].f1||tr[k].f2)
    {
        int l = tr[k].l,r = tr[k].r;
        int mid=(l+r)>>1;
		change(tr[k<<1],l,mid,tr[k].f1,tr[k].f2);
		int pos=mid-l+2;
        LL t1 = (f[pos-1]*tr[k].f2+f[pos-2]*tr[k].f1)%mod;
        LL t2 = (f[pos]*tr[k].f2+f[pos-1]*tr[k].f1)%mod;
		change(tr[k<<1|1],mid+1,r,t1,t2);
		tr[k].f1=0,tr[k].f2=0;
    }
}

void modify(int u,int l,int r)
{
    if(l<=tr[u].l&&tr[u].r<=r)
    {
        int L = tr[u].l,R = tr[u].r;
        change(tr[u],L,R,f[L-l+1],f[L-l+2]);
        return ;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if(l<=mid) modify(u<<1,l,r);
    if(r>mid) modify(u<<1|1,l,r);
    pushup(u);
}

LL query(int u,int l,int r)
{
    if(l<=tr[u].l&&tr[u].r<=r) return tr[u].v;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    LL res = 0;
    if(l<=mid) res = (1ll*res + query(u<<1,l,r))%mod;
    if(r>mid) res = (1ll*res + query(u<<1|1,l,r))%mod;
    return res;
}

int main()
{
    ios;    
    cin>>n>>m;
    f[1] = f[2] = 1;
    for(int i=3;i<=n+1;i++) f[i] = (f[i-1] + f[i-2])%mod;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(m--)
    {
        int op,l,r;cin>>op>>l>>r;
        if(op==1) modify(1,l,r);
        else cout<<query(1,l,r)<<'\n';
    }
    return 0;
}