Codeforces 718D (线段树维护矩阵)

Codeforces 718D
题意：给出一个$n$长序列$a_i$，维护以下操作
1、1 l r x，将$a_{i \in [l,r]}$加上$x$
2、2 l r，求$\sum\limits_{i=l}^r F(a_i)$，$F(a_i)$为斐波那契的第$x$项

斐波那契数列考虑矩阵，那么这里我们可以用线段树维护矩阵 (矩阵满足结合律，则可以轻松合并信息)

区间加一个数相当于矩阵乘多少次转移矩阵，最后答案乘上起始矩阵即可。

线段树维护$lazy$表示当前的标记 (是一个矩阵)，$sum$表示当前区间的和 (矩阵和)

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 100000 + 5;
    const LL MO = 1e9 + 7;

    int n, Q;

    struct matrix {
        LL a[2][2];
        matrix() {ms(a, 0);}
        void init() {for (int i = 0; i < 2; ++i) a[i][i] = 1;}
    } f, tr;
    matrix mul(matrix a, matrix b) {
        matrix ret;
        for (int i = 0; i < 2; ++i) 
        for (int j = 0; j < 2; ++j)
        for (int k = 0; k < 2; ++k) (ret.a[i][j] += a.a[i][k] * b.a[k][j] % MO) %= MO;
        return ret;
    }
    matrix ksm(matrix a, int b) {
        matrix ans, bs = a; ans.init();
        while (b) {
            if (b & 1) ans = mul(ans, bs);
            bs = mul(bs, bs);
            b >>= 1;
        }
        return ans;
    }
    matrix add(matrix a, matrix b) {
        matrix ret;
        for (int i = 0; i < 2; ++i) 
        for (int j = 0; j < 2; ++j) (ret.a[i][j] += a.a[i][j] + b.a[i][j]) %= MO;
        return ret;
    }

    #define lc (o << 1)
    #define rc (o << 1 | 1)
    #define M ((l + r) >> 1)
    #define ls lc, l, M
    #define rs rc, M + 1, r

    matrix sum[MAXN * 4], lazy[MAXN * 4];
    void pushup(int o) {
        sum[o] = sum[lc];
        sum[o] = add(sum[o], sum[rc]);
    }
    void pushdown(int o) {
        sum[lc] = mul(sum[lc], lazy[o]);
        sum[rc] = mul(sum[rc], lazy[o]);
        lazy[lc] = mul(lazy[lc], lazy[o]);
        lazy[rc] = mul(lazy[rc], lazy[o]);
        lazy[o] = matrix(), lazy[o].init();
    }
    void build(int o, int l, int r) {
        lazy[o].init(), sum[o].init();
        if (l == r) return ;
        build(ls), build(rs);
        pushup(o);
    }
    void update(int o, int l, int r, int x, int y, matrix p) {
        if (!(l == r)) pushdown(o);
        if (x <= l && r <= y) {
            sum[o] = mul(sum[o], p);
            lazy[o] = mul(lazy[o], p);
            return ;
        }
        if (x <= M) update(ls, x, y, p);
        if (M < y) update(rs, x, y, p);
        pushup(o);
    }
    matrix query(int o, int l, int r, int x, int y) {
        if (!(l == r)) pushdown(o);
        if (x <= l && r <= y) {
            return sum[o];
        }
        matrix ret; 
        if (x <= M) ret = add(ret, query(ls, x, y));
        if (M < y) ret = add(ret, query(rs, x, y));
        return ret;
    }

    void clean() {
    }
    int solve() {

        tr.a[0][0] = 0, tr.a[0][1] = 1;
        tr.a[1][0] = 1, tr.a[1][1] = 1;
        f.a[0][0] = 0, f.a[0][1] = 1;

        clean();
        cin >> n >> Q;
        build(1, 1, n);
        for (int c, i = 1; i <= n; ++i) {
            scanf("%d", &c);
            update(1, 1, n, i, i, ksm(tr, c - 1));
        }
        while (Q--) {
            int tp, l, r, c; scanf("%d%d%d", &tp, &l, &r);
            if (tp == 1) {
                scanf("%d", &c);
                update(1, 1, n, l, r, ksm(tr, c));
            } else {
                printf("%lld\n", mul(f, query(1, 1, n, l, r)).a[0][1]);
            }
        }

        return 0;
    }  
}
int main() {
    flyinthesky::solve();
    return 0;
}