codeforces 446C DZY Loves Fibonacci Numbers 线段树

假如F[1] = a, F[2] = B, F[n] = F[n - 1] + F[n - 2]。

写成矩阵表示形式可以很快发现F[n] = f[n - 1] * b + f[n - 2] * a。 f[n] 是斐波那契数列

也就是我们如果知道一段区间的前两个数增加了多少，可以很快计算出这段区间的第k个数增加了多少

通过简单的公式叠加也能求和

F[n] = f[n - 1] * b + f[n - 2] * a

F[n - 1] = f[n - 2] * b + f[n - 3] * a

.....

F[3] = f[2] * b + f[1] * a

F[2] = 1 * b + 0

F[1] = 0 + a

令G[n] = 0 + 1 + f[2] + f[3] + .... + f[n - 1]

K[n] = 1 + 0 + f[1] + f[2] + .... f[n - 2] ，那么F[n] = G[n] * b + K[n] * a

线段树结点维护a,b两个延迟标记，分别表示第一个数和第二个数增加了多少

注意在PushDown和update的时候还要通过F[n] = f[n - 1] * b + f[n - 2] * a计算出右子节点的前两个数应该增加的值

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <iostream>

using namespace std;

typedef long long LL;

const int maxn = 3e5 + 10;

const int mod = 1e9 + 9;

#define lson idx << 1, l, mid

#define rson idx << 1 | 1, mid + 1, r

LL f[maxn], F[maxn], G[maxn];

void init() {

    f[1] = G[1] = 1;

    F[0] = 1;

    F[1] = 1;

    for(int i = 2; i < maxn; i++) {

        f[i] = (f[i - 1] + f[i - 2]) % mod;

        G[i] = (G[i - 1] + f[i]) % mod;

        F[i] = (F[i - 1] + f[i - 1]) % mod;

    }

    // F[i] = 1 + 0 + f[1] + f[2] + f[3] + ....f[i - 1]

    // G[i] = 0 + f[1] + f[2] + f[3] + ....f[i]

}

LL sum[maxn << 2];

LL a[maxn << 2], b[maxn << 2];

void PushUp(int idx) {

    sum[idx] = (sum[idx << 1] + sum[idx << 1 | 1]) % mod;

}

void build(int idx, int l, int r) {

    a[idx] = b[idx] = 0;

    if(l == r) {

        scanf("%I64d", &sum[idx]);

    } else {

        int mid = (r + l) >> 1;

        build(lson);

        build(rson);

        PushUp(idx);

    }

}

void maintain(int idx, int l,int r, int v1, int v2) {

    int len = r - l + 1;

    a[idx] = (a[idx] + v1) % mod;

    b[idx] = (b[idx] + v2) % mod;

    sum[idx] = (sum[idx] + G[len - 1] * v2 % mod + F[len - 1] * v1 % mod) % mod;

}

void PushDown(int idx, int l, int r) {

    if(a[idx] != 0 || b[idx] != 0) {

         int mid = (r + l) >> 1;

         maintain(lson, a[idx], b[idx]);

         int len = mid - l + 1;

         int v1 = (f[len] * b[idx] + f[len - 1] * a[idx]) % mod;

         int v2 = (f[len + 1] * b[idx] + f[len] * a[idx]) % mod;

         maintain(rson, v1, v2);

         a[idx] = b[idx] = 0;

    }

}

void update(int idx, int l, int r, int tl, int tr, int v1, int v2) {

    if(tl <= l && tr >= r) {

        maintain(idx, l, r, v1, v2);

    } else {

        PushDown(idx, l, r);

        int mid = (r + l) >> 1;

        if(tl <= mid) update(lson, tl, tr, v1, v2);

        if(tr > mid) {

            LL h1 = v1, h2 = v2;

            if(tl <= mid) {

                int len = mid - max(tl,l) + 1;

                h1 = (f[len] * v2 + f[len - 1] * v1) % mod;

                h2 = (f[len + 1] * v2 + f[len] * v1) % mod;

            }

            update(rson, tl, tr, h1, h2);

        }

        PushUp(idx);

    }

}

LL query(int idx, int l, int r, int tl, int tr) {

    if(tl <= l && tr >= r) return sum[idx];

    else {

        PushDown(idx, l, r);

        int mid = (r + l) >> 1;

        LL ans = 0;

        if(tl <= mid) ans = (ans + query(lson, tl, tr)) % mod;

        if(tr > mid) ans = (ans + query(rson, tl, tr)) % mod;

        return ans;

    }

}

int main() {

    init();

    int n, m;

    scanf("%d%d", &n, &m);

    build(1, 1, n);

    for(int i = 1; i <= m; i++) {

        int op, l, r;

        scanf("%d%d%d", &op, &l, &r);

        if(op == 1) update(1, 1, n, l, r, 1, 1);

        else {

            LL ans = query(1, 1, n, l, r);

            printf("%I64d\n", ans);

        }

    }

    return 0;

}

巴特西

codeforces 446C DZY Loves Fibonacci Numbers 线段树

最新文章

热门文章