Codeforces 316E3 线段树 + 斐波那切数列 (看题解)

最关键的一点就是

f[ 0 ] * a[ 0 ] + f[ 1 ] * a[ 1 ] + ... + f[ n - 1] * a[ n  - 1]

f[ 1 ] * a[ 0 ] + f[ 2 ] * a[ 1 ] + ... + f[ n ] * a[ n  - 1]

f[ 2 ] * a[ 0 ] + f[ 3 ] * a[ 1 ] + ... + f[ n + 1] * a[ n  - 1]

......

这也是满足斐波那切的性质

也就是说，系数的斐波那切的多项式也能向斐波那切一样递推。

然后我们在线段树上保存系数为f[ 0 ]开始的多项式的值和系数为f[ 1 ]开始的多项式的值。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long

using namespace std;

const int N = 2e5 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const double PI = acos(-1);

void add(int& a, int b) {
    a += b; if(a >= mod) a -= mod;
}

int mat[N][2][2], f[N], g[N];

void print(int o) {
    puts("");
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 2; j++) {
            printf("%d ", mat[o][i][j]);
        }
        puts("");
    }
}

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
int f0[N << 2], f1[N << 2];
int lazy[N << 2];

inline int getVal(int f0, int f1, int k) {
    if(k == 0) return f0;
    else if(k == 1) return f1;
    else return (1LL * mat[k - 1][0][0] * f1 % mod + 1LL * mat[k - 1][0][1] * f0 % mod) % mod;
}
void pull(int rt, int l, int r) {
    int mid = l + r >> 1;
    f0[rt] = f0[rt << 1];
    f1[rt] = f1[rt << 1];
    add(f0[rt], getVal(f0[rt << 1 | 1], f1[rt << 1 | 1], mid - l + 1));
    add(f1[rt], getVal(f0[rt << 1 | 1], f1[rt << 1 | 1], mid - l + 2));
}
void push(int rt, int l, int r) {
    int mid = l + r >> 1;
    if(lazy[rt]) {
        add(lazy[rt << 1], lazy[rt]);
        add(lazy[rt << 1 | 1], lazy[rt]);
        add(f0[rt << 1], 1LL * lazy[rt] * f[mid - l] % mod);
        add(f0[rt << 1 | 1], 1LL * lazy[rt] * f[r - mid - 1] % mod);
        add(f1[rt << 1], 1LL * lazy[rt] * g[mid - l] % mod);
        add(f1[rt << 1 | 1], 1LL * lazy[rt] * g[r - mid - 1] % mod);
        lazy[rt] = 0;
    }
}
void build(int l, int r, int rt) {
    if(l == r) {
        scanf("%d", &f0[rt]);
        f1[rt] = f0[rt];
        return;
    }
    int mid = l + r >> 1;
    build(lson); build(rson);
    pull(rt, l, r);
}
void update(int L, int R, int d, int l, int r, int rt) {
    if(r < L || R < l) return;
    if(L <= l && r <= R) {
        add(f0[rt], 1LL * d * f[r - l] % mod);
        add(f1[rt], 1LL * d * g[r - l] % mod);
        add(lazy[rt], d);
        return ;
    }
    push(rt, l, r);
    int mid = l + r >> 1;
    update(L, R, d, lson);
    update(L, R, d, rson);
    pull(rt, l, r);
}
int query(int L, int R, int l, int r, int rt) {
    if(r < L || R < l) return 0;
    if(L <= l && r <= R) return getVal(f0[rt], f1[rt], l - L);
    push(rt, l, r);
    int mid = l + r >> 1;
    return (query(L, R, lson) + query(L, R, rson)) % mod;
}

int n, m;
int main() {
    mat[0][0][0] = 1; mat[0][0][1] = 0;
    mat[0][1][0] = 0; mat[0][1][1] = 1;
    mat[1][0][0] = mat[1][0][1] = 1;
    mat[1][1][0] = 1; mat[1][1][1] = 0;
    for(int o = 2; o < N; o++) {
        for(int i = 0; i < 2; i++)
            for(int j = 0; j < 2; j++)
                for(int k = 0; k < 2; k++)
                    mat[o][i][j] = (mat[o][i][j] + 1LL * mat[1][i][k] * mat[o - 1][k][j] % mod) % mod;
    }
    f[0] = f[1] = 1;
    for(int i = 2; i < N; i++) f[i] = (f[i - 1] + f[i - 2]) % mod;
    for(int i = 1; i < N; i++) add(f[i], f[i - 1]);
    g[0] = 1, g[1] = 2;
    for(int i = 2; i < N; i++) g[i] = (g[i - 1] + g[i - 2]) % mod;
    for(int i = 1; i < N; i++) add(g[i], g[i - 1]);

    scanf("%d%d", &n, &m);
    build(1, n, 1);
    while(m--) {
        int op;
        scanf("%d", &op);
        if(op == 1) {
            int x, v;
            scanf("%d%d", &x, &v);
            int ret = query(x, x, 1, n, 1);
            update(x, x, -ret, 1, n, 1);
            update(x, x, v, 1, n, 1);
        } else if(op == 2) {
            int L, R;
            scanf("%d%d", &L, &R);
            printf("%d
", query(L, R, 1, n, 1));
        } else {
            int L, R, d;
            scanf("%d%d%d", &L, &R, &d);
            update(L, R, d, 1, n, 1);
        }
    }
    return 0;
}

/*
*/