首页 > 代码库 > codeforces 446C DZY Loves Fibonacci Numbers 线段树

codeforces 446C DZY Loves Fibonacci Numbers 线段树

2024-07-14 23:53:34   221人阅读

假如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, rLL 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;}
View Code


联系
我们