【CF446C】DZY Loves Fibonacci Numbers（线段树）

Description

给定一个序列，资瓷区间加上一个斐波那契数列，区间求和。

Solution

有一个性质：

fib[a+b]=fib[a−1]×fib[b]+fib[a]×fib[b+1] f i b [ a + b ] = f i b [ a − 1 ] × f i b [ b ] + f i b [ a ] × f i b [ b + 1 ]

对于每次操作[l,r] [ l , r ] ，ai+=fib[i−l+1] a i + = f i b [ i − l + 1 ] ，根据上面那个性质，有：

ai+=fib[i]×fib[−l]+fib[i+1]×fib[1−l] a i + = f i b [ i ] × f i b [ − l ] + f i b [ i + 1 ] × f i b [ 1 − l ]

用两棵线段树分别维护

fib[i],fib[i−1] f i b [ i ] , f i b [ i − 1 ] 即可。

Code

/************************************************
 * Au: Hany01
 * Date: Aug 24th, 2018
 * Prob: CF446 C

 * Inst: Yali High School
************************************************/

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
#define rep(i, j) for (register int i = 0, i##_end_ = (j); i < i##_end_; ++ i)
#define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define x first
#define y second
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define SZ(a) ((int)(a).size())
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define y1 wozenmezhemecaia

template <typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }

inline int read() {
    static int _, __; static char c_;
    for (_ = 0, __ = 1, c_ = getchar(); c_ < '0' || c_ > '9'; c_ = getchar()) if (c_ == '-') __ = -1;
    for ( ; c_ >= '0' && c_ <= '9'; c_ = getchar()) _ = (_ << 1) + (_ << 3) + (c_ ^ 48);
    return _ * __;
}

const int maxn = 3e5 + 5, MOD = 1e9 + 9;

int n, fib[maxn], _fib[maxn], sum[maxn], m, l, r, ty;

inline int ad(int x, int y) { if ((x += y) >= MOD) return x - MOD; return x; }

struct SegmentTree {
    int tag[maxn << 2], sm[maxn << 2], pre[maxn];
#define lc (t << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)
    inline void pushdown(int t, int l, int r) {
        if (tag[t]) {
            tag[lc] = ad(tag[lc], tag[t]), tag[rc] = ad(tag[rc], tag[t]);
            sm[lc] = ad(sm[lc], (LL)ad(pre[mid], MOD - pre[l - 1]) * tag[t] % MOD);
            sm[rc] = ad(sm[rc], (LL)ad(pre[r], MOD - pre[mid]) * tag[t] % MOD);
            tag[t] = 0;
        }
    }
    inline void maintain(int t) { sm[t] = ad(sm[lc], sm[rc]); }
    void update(int t, int l, int r, int x, int y, int dt) {
        if (x <= l && r <= y) {
            tag[t] = ad(tag[t], dt), sm[t] = ad(sm[t], (LL)dt * ad(pre[r], MOD - pre[l - 1]) % MOD);
            return;
        }
        pushdown(t, l, r);
        if (x <= mid) update(lc, l, mid, x, y, dt);
        if (y >  mid) update(rc, mid + 1, r, x, y, dt);
        maintain(t);
    }
    int query(int t, int l, int r, int x, int y) {
        if (x <= l && r <= y) return sm[t];
        pushdown(t, l, r);
        if (y <= mid) return query(lc, l, mid, x, y);
        if (x >  mid) return query(rc, mid + 1, r, x, y);
        return ad(query(lc, l, mid, x, y), query(rc, mid + 1, r, x, y));
    }
}ST1, ST2;

int main()
{
#ifdef hany01
    freopen("cf446c.in", "r", stdin);
    freopen("cf446c.out", "w", stdout);
#endif

    n = read(), m = read();
    For(i, 1, n) sum[i] = ad(read(), sum[i - 1]);
    fib[1] = _fib[1] = 1;
    For(i, 2, n + 1) fib[i] = ad(fib[i - 1], fib[i - 2]);
    For(i, 2, n + 1) _fib[i] = ad(_fib[i - 2], MOD - _fib[i - 1]);
    For(i, 1, n) ST1.pre[i] = ad(fib[i], ST1.pre[i - 1]), ST2.pre[i] = ad(fib[i + 1], ST2.pre[i - 1]);
    while (m --) {
        ty = read(), l = read(), r = read();
        if (ty == 1) ST1.update(1, 1, n, l, r, _fib[l]), ST2.update(1, 1, n, l, r, _fib[l - 1]);
        else printf("%d\n", ad(ad(sum[r], MOD - sum[l - 1]), ad(ST1.query(1, 1, n, l, r), ST2.query(1, 1, n, l, r))));
    }

    return 0;
}