8.CF446C DZY Loves Fibonacci Numbers 线段树Lazy标记

8.CF446C DZY Loves Fibonacci Numbers 线段树Lazy标记

给定序列，要求支持区间对应项加斐波那契数列，区间求和

洛谷传送门：​​CF446C DZY Loves Fibonacci Numbers - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)​​

CF传送门：​​C. DZY Loves Fibonacci Numbers (codeforces.com)​​

题目分析

给定序列，要求支持区间对应项加斐波那契数列，区间求和
考虑广义斐波那契数列：在一个区间加斐波那契数列后，区间会保持斐波那契数列的性质

考虑对每个区间维护两个标记，分别表示, 标记下放时计算加和。

标记下放略微复杂，理清楚就好。注意标记下放给左右子节点标记时也需要考虑斐波那契性质的影响！

Code

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

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

int fab[N];

inline void init(){
    fab[1] = fab[2] = 1;
    for(int i = 3; i <= 3e5 + 2; i++) fab[i] = (fab[i - 1] + fab[i - 2]) % MOD;
}

namespace SegTree{
    #define ls rt << 1
    #define rs rt << 1 | 1
    #define lson ls, l,
    #define rson rs, mid + 1,

    int tree[N << 2], tag[N << 2][2];

    inline void push_up(int rt){ tree[rt] = (tree[ls] + tree[rs]) % MOD; }

    inline void push_down(int rt, int l, int r){
        if(!tag[rt][0] && !tag[rt][1]) return;
        int mid = l + r >> 1;
        (tag[ls][0] += tag[rt][0]) %= MOD;
        (tag[ls][1] += tag[rt][1]) %= MOD;
        (tree[ls] += tag[rt][0] * fab[mid - l + 1] % MOD + tag[rt][1] * (fab[mid - l + 2] - 1) % MOD) %= MOD;
        (tag[rs][0] += tag[rt][0] * fab[mid - l] % MOD + tag[rt][1] * fab[mid - l + 1] % MOD) %= MOD;
        (tag[rs][1] += tag[rt][0] * fab[mid - l + 1] % MOD + tag[rt][1] * fab[mid - l + 2] % MOD) %= MOD;
        (tree[rs] += (tag[rt][0] * fab[r - l + 1] + tag[rt][1] * (fab[r - l + 2] - 1)) - (tag[rt][0] * fab[mid - l + 1] + tag[rt][1] * (fab[mid - l + 2] - 1))) %= MOD;
        tag[rt][0] = tag[rt][1] = 0;    
    }

    void build(int rt, int l, int r){
        tag[rt][0] = tag[rt][1] = 0;
        if(l == r){
            cin >> tree[rt];
            return;
        }
        int mid = l + r >> 1;
        build(lson), build(rson);
        push_up(rt);
    }

    void update(int rt, int l, int r, int L, int R){
        if(l >= L && r <= R){
            int a_1 = fab[l - L + 1], a_2 = fab[l - L + 2];
            (tag[rt][0] += a_1) %= MOD;
            (tag[rt][1] += a_2) %= MOD;
            (tree[rt] += a_1 * fab[r - l + 1] % MOD + a_2 * (fab[r - l + 2] - 1) % MOD) %= MOD;
            return;
        }
        push_down(rt, l, r);
        int mid = l + r >> 1;
        if(mid >= L) update(lson, L, R);
        if(mid < R) update(rson, L, R);
        push_up(rt);
    }

    int query(int rt, int l, int r, int L, int R){
        if(l >= L && r <= R) return tree[rt];
        push_down(rt, l, r);
        int mid = l + r >> 1, ans = 0;
        if(mid >= L) (ans += query(lson, L, R)) %= MOD;
        if(mid < R) (ans += query(rson, L, R)) %= MOD;
        return ans;
    }

}

#define SEGRG 1, 1,

inline void solve(){
    int n, m; cin >> n >> m;
    SegTree::build(SEGRG);
    while(m--){
        int op, l = 0, r = 0; cin >> op >> l >> r;
        if(op == 1){
            SegTree::update(SEGRG, l, r);
        } else {
            cout << (SegTree::query(SEGRG, l, r) % MOD + MOD) % MOD << endl;
        }
    }
}

signed main(){
    init();
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}