传送门

一道纯粹的码力 + 卡常题。

矩阵乘法，线段树。

线段树存矩阵。

构造迭代矩阵：

\[\begin{pmatrix}f_i&f_{i-1}\end{pmatrix}\times\begin{pmatrix}1&1\\1&0\end{pmatrix}=\begin{pmatrix}f_{i+1}&f_{i}\end{pmatrix}
\]

\[\begin{pmatrix}f_i&f_{i-1}\end{pmatrix}\times\begin{pmatrix}0&1\\1&-1\end{pmatrix}=\begin{pmatrix}f_{i-1}&f_{i-2}\end{pmatrix}
\]

另外矩阵乘法满足分配律，于是父结点矩阵为子结点矩阵之和。

然后就很清楚了。

先把要用的矩阵处理出来。

\(add\) 操作就是直接乘。

\(set\) 操作就直接覆盖即可。

两个标记 \(add\) 和 \(set\)，维护一下即可。

能用位运算尽量位运算。

快速幂不要递归求。

存矩阵不要用 \(a[2][2]\)，用 \(a,b,c,d\) 分别表示矩阵的四项。

\(a,b,c,d\) 不要开 \(longlong\)，考虑取模 \(10^9+7\)，矩阵加法不会溢出，矩阵乘法先转 \(longlong\) 再取模，要快很多。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
#define ri register int
const int N = 5e5 + 10, MOD = 1e9 + 7;

inline LL read () {
    LL num = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') num = num * 10 + (c ^ 48), c = getchar();
    return num * f;
}

int mod (int x) {
    return (x % MOD + MOD) % MOD;
}

struct matrix {
    int a, b, c, d;
    void clear () {
        a = b = c = d = 0;
    }
    friend matrix operator + (const matrix &x, const matrix &y) {
        matrix ans;
        ans.a = mod(x.a + y.a);
        ans.b = mod(x.b + y.b);
        ans.c = mod(x.c + y.c);
        ans.d = mod(x.d + y.d);
        return ans;
    }
    friend matrix operator * (const matrix &x, const matrix &y) {
        matrix ans;
        ans.a = mod(1ll * x.a * y.a % MOD + 1ll * x.b * y.c % MOD);
        ans.b = mod(1ll * x.a * y.b % MOD + 1ll * x.b * y.d % MOD);
        ans.c = mod(1ll * x.c * y.a % MOD + 1ll * x.d * y.c % MOD);
        ans.d = mod(1ll * x.c * y.b % MOD + 1ll * x.d * y.d % MOD);
        return ans;
    }
};

const matrix st = (matrix){1, 0, 0, 1}, fibnxt = (matrix){1, 1, 1, 0}, fib = (matrix){1, 1, 0, 0}, fibpre = (matrix){0, 1, 1, -1};

matrix mat_qpow (matrix x, LL b) {
    matrix res = st;
    while (b) {
        if (b & 1) res = res * x;
        b >>= 1; x = x * x;
    }
    return res;
}

int n, m;
LL a[N];

struct node {
    int l, r, cset;
    matrix mat, add, sett;
}tree[N << 2];

inline void push_up (int p) {
    tree[p].mat = tree[p << 1].mat + tree[p << 1 | 1].mat;
}

inline void update (int p, matrix x) {
    if (!tree[p].cset) tree[p].add = tree[p].add * x;
    else tree[p].sett = tree[p].sett * x;
    tree[p].mat = tree[p].mat * x;
    return;
}

inline void push_down (int p) {
    if (tree[p].cset) {
        int ll = tree[p << 1].r - tree[p << 1].l + 1; int lr = tree[p << 1 | 1].r - tree[p << 1 | 1].l + 1;
        tree[p << 1].add = tree[p << 1 | 1].add = st;
        tree[p << 1].sett = tree[p << 1 | 1].sett = tree[p].sett;
        tree[p << 1].mat = (matrix){ll, 0, 0, ll} * tree[p].sett;
        tree[p << 1 | 1].mat = (matrix){lr, 0, 0, lr} * tree[p].sett;
        tree[p << 1].cset = tree[p << 1 | 1].cset = 1;
        tree[p].cset = 0;
    }
    else {
        update(p << 1, tree[p].add); update(p << 1 | 1, tree[p].add);
        tree[p].add = st;
    }
}

void build (int p, int l, int r) {
    tree[p].l = l, tree[p].r = r; tree[p].add = st;
    if (l == r) {
        tree[p].mat = fib * mat_qpow(fibnxt, a[l] - 1);
        return;
    }
    int mid = (l + r) >> 1;
    build (p << 1, l, mid); build (p << 1 | 1, mid + 1, r);
    push_up(p);
}

void add (int p, int l, int r, matrix x) {
    int tl = tree[p].l, tr = tree[p].r;
    if (tl >= l && tr <= r) {
        update(p, x);
        return;
    }
    push_down(p);
    int mid = (tl + tr) >> 1;
    if (l <= mid) add (p << 1, l, r, x);
    if (r > mid) add (p << 1 | 1, l, r, x);
    push_up(p);
}

void sett (int p, int l, int r, matrix x) {
    int tl = tree[p].l, tr = tree[p].r;
    if (tl >= l && tr <= r) {
        tree[p].cset = 1;
        int ll = tr - tl + 1;
        tree[p].mat = (matrix){ll, 0, 0, ll} * x;
        tree[p].sett = x;
        tree[p].add = st;
        return;
    }
    push_down(p);
    int mid = (tl + tr) >> 1;
    if (l <= mid) sett (p << 1, l, r, x);
    if (r > mid) sett (p << 1 | 1, l, r, x);
    push_up(p);
}

int stk[N << 4], ed;

matrix query (int p, int l, int r) {
    int tl = tree[p].l, tr = tree[p].r;
    if (tl >= l && tr <= r) return tree[p].mat;
    push_down(p);
    int mid = (tl + tr) >> 1;
    matrix res; res.clear();
    if (l <= mid) res = res + query (p << 1, l, r);
    if (r > mid) res = res + query (p << 1 | 1, l, r);
    return res;
}

int main () {
//    freopen("data10.in", "r", stdin);
//    freopen("data10.ans", "w", stdout);
    n = read();
    for (ri i = 1;i <= n;++i) a[i] = read();
    build (1, 1, n);
    m = read();
    while (m--) {
        int op = read(), l = read(), r = read(), x;
        if (op == 1) {
            x = read();
            matrix mat;
            if (x < 0) mat = mat_qpow(fibpre, -x);
            else mat = mat_qpow(fibnxt, x);
            add(1, l, r, mat);
        }
        else if (op == 2) {
            x = read();
            matrix mat = fib * mat_qpow(fibnxt, x - 1);
            sett(1, l, r, mat);
        }
        else printf("%lld\n", query(1, l, r).b);
    }
    return 0;
}