【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
 * Email: [email protected] & [email protected]
 * 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,  : ; }
template <typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b,  : ; }

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

const int maxn =  + , MOD =  + ;

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 << ], sm[maxn << ], 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 - ]) * tag[t] % MOD);
            sm[rc] = ad(sm[rc], (LL)ad(pre[r], MOD - pre[mid]) * tag[t] % MOD);
            tag[t] = ;
        }
    }
    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 - ]) % MOD);
            return;
        }
        pushdown(t, l, r);
        if (x <= mid) update(lc, l, mid, x, y, dt);
        if (y >  mid) update(rc, mid + , 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 + , r, x, y);
        return ad(query(lc, l, mid, x, y), query(rc, mid + , 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, , n) sum[i] = ad(read(), sum[i - ]);
    fib[] = _fib[] = ;
    For(i, , n + ) fib[i] = ad(fib[i - ], fib[i - ]);
    For(i, , n + ) _fib[i] = ad(_fib[i - ], MOD - _fib[i - ]);
    For(i, , n) ST1.pre[i] = ad(fib[i], ST1.pre[i - ]), ST2.pre[i] = ad(fib[i + ], ST2.pre[i - ]);
    while (m --) {
        ty = read(), l = read(), r = read();
        if (ty == ) ST1.update(, , n, l, r, _fib[l]), ST2.update(, , n, l, r, _fib[l - ]);
        else printf("%d\n", ad(ad(sum[r], MOD - sum[l - ]), ad(ST1.query(, , n, l, r), ST2.query(, , n, l, r))));
    }

    return ;
}