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

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

个人Limitの线段树题单题解主目录：Limitの线段树题单 题解目录_HeartFireY的博客-CSDN博客

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

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

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

题目分析

给定序列，要求支持区间对应项加斐波那契数列，区间求和 考虑广义斐波那契数列：在一个区间加斐波那契数列后，区间会保持斐波那契数列的性质 ∑ i = 1 n a i = f n × a 1 + ( f n + 1 − 1 ) × a 2 \sum^n_{i = 1}a_i = f_n \times a_1 + (f_{n + 1} - 1) \times a_2 i=1∑n​ai​=fn​×a1​+(fn+1​−1)×a2​ 考虑对每个区间维护两个 L a z y Lazy Lazy标记，分别表示 a 1 , a 2 a_1, a_2 a1​,a2​, 标记下放时计算加和。

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

Code

#include 
#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 = L) update(lson, L, R);
        if(mid = L && r > 1, ans = 0;
        if(mid >= L) (ans += query(lson, L, R)) %= MOD;
        if(mid > 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