题意

定义 $fi{b}_n$fibn​为斐波那契数列(即 $f_1=f_2=1,f_n=f_{n-1}+f_{n-2}$f1​=f2​=1,fn​=fn−1​+fn−2​)

$fi{c}_n={\sum }_{i=1}^{n}fi{b}_i$ficn​=∑i=1n​fibi​,

$fi{d}_n={\sum }_{i=1}^{n}fi{c}_i$fidn​=∑i=1n​fici​

现给一个序列 $a_1,a_2,...,a_n$a1​,a2​,...,an​，给 $q$q次操作，每次操作有两种选项:

1. $1lrx$1 l r x 修改 $a\left[l...r\right]$a[l...r]区间+x.
2. $2lr$2 l r 查询 ${\sum }_{i=l}^{r}fi{d}_{a\left[i\right]}$∑i=lr​fida[i]​的值.

做法

$fi{c}_n={\sum }_{i=1}^{n}fi{b}_i+fi{b}_2-fi{b}_2=fi{b}_{n+2}-1.$ficn​=∑i=1n​fibi​+fib2​−fib2​=fibn+2​−1.

$fi{d}_n={\sum }_{i=1}^{n}fi{c}_i={\sum }_{i=1}^{n}fi{c}_{i+2}+fi{c}_4-fi{c}_4-n=fi{b}_{n+4}-(n+3).$fidn​=∑i=1n​fici​=∑i=1n​fici+2​+fic4​−fic4​−n=fibn+4​−(n+3).

考虑用线段树维护矩阵以及区间和.
另外由于 $lazy$lazy标记的存在转移矩阵的次幂会重复用很多次, 因此使用hash来优化.

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define clr(a, b) memset(a, b, sizeof a)
const int mod = 1e8 + 7;
const int mm = 200000016;
const int N = 1 << 19 | 7;
template<int S>
struct Mat{
#define rep(i) for(int i = 0; i < S; i++)
    int e[S][S];
    void clear() { clr(e, 0);}
    Mat() { clear();}
    void E() { clear();rep(i)e[i][i]=1;}
    Mat(vector<vector<int>>a){
        rep(i)rep(j) e[i][j]=a[i][j];
    }
    int* operator[](int i){return e[i];}
    Mat operator + (Mat&rhs) {
        Mat ret;
        rep(i)rep(j)ret[i][j]=(e[i][j]+rhs[i][j])%mod;
        return ret;
    }
    Mat operator * (Mat&rhs) {
        Mat ret;
        rep(i)rep(k)if(e[i][k])rep(j)
            (ret[i][j]+=1ll*e[i][k]*rhs[k][j]%mod)%=mod;
        return ret;
    }
    Mat operator ^ (ll n) {
        n %= mm; // A ^ mm = I
        static Mat a;
        Mat ret; ret.E();
        for(a=*this;n;n>>=1,a=a*a)
            if(n&1) ret=ret*a;
        return ret;
    }
    void print() {
        rep(i)rep(j)cerr<<e[i][j]<<" \n"[j==S-1];
    }
#undef rep
};
Mat<2> A({{1,1},{1,0}});
const ll o[2] = {5, 3};
int a[N];
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
__gnu_pbds::cc_hash_table<ll, Mat<2>> hs;
Mat<2> calc(ll x) {
    x %= mm;
    if(hs.find(x)!=hs.end()) return hs[x];
    return hs[x] = A ^ x;
}
struct Node {
    int v;
    ll tag;
    Mat<2> w;
} tree[N];
#define ls rt << 1
#define rs rt<<1|1
void push_up(int rt) {
    tree[rt].v = (tree[ls].v + tree[rs].v) % mod;
    tree[rt].w = tree[ls].w + tree[rs].w;
}
void push_down(int rt, int l, int r) {
    ll& tag=tree[rt].tag;
    if(tag) {
        Mat<2> temp = calc(tag);
        tree[ls].tag += tag;
        tree[rs].tag += tag;
        tree[ls].w = tree[ls].w * temp;
        tree[rs].w = tree[rs].w * temp;
        int mid = (l + r) >> 1;
        (tree[ls].v += tag % mod * (mid - l + 1ll) % mod) %= mod;
        (tree[rs].v += tag % mod * (r-mid) % mod) %= mod;
        tag = 0;
    }
}
void build(int rt, int l, int r) {
    if(l == r) {
        tree[rt].w = calc(a[l] - 1);
        tree[rt].v = a[l] + 3;
    } else {
        int mid = (l + r) >> 1;
        build(ls, l, mid), build(rs, mid + 1, r);
        push_up(rt);
    }
}
void update(int rt, int l, int r, int L, int R, int x) {
    if(L <= l && r <= R) {
        Mat<2> temp = calc(x);
        tree[rt].w = tree[rt].w * temp;
        tree[rt].tag += x;
        (tree[rt].v += (r-l+1ll)*x%mod)%=mod;
        return;
    }
    push_down(rt, l, r);
    int mid = (l + r) >> 1;
    if(mid >= L) update(ls, l, mid, L, R, x);
    if(mid < R) update(rs, mid + 1, r, L, R, x);
    push_up(rt);
}

int query(int rt, int l, int r, int L, int R) {
    if(L <= l && r <= R) {
        int ret = mod - tree[rt].v;
        for(int i = 0; i < 2; i++)
            ret = (ret + o[i] * tree[rt].w[i][0] % mod) % mod;
        return ret;
    }
    push_down(rt, l, r);
    int mid = (l + r) >> 1, ret = 0;
    if(mid >= L) ret = (ret + query(ls, l, mid, L, R)) % mod;
    if(mid < R) ret = (ret + query(rs, mid + 1, r, L, R)) % mod;
    return ret;
}

int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // local
    int n, q; scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", a + i);
    build(1, 1, n);
    scanf("%d", &q);
    for(int i = 0, op, l, r, x; i < q; i++) {
        scanf("%d%d%d", &op, &l, &r);
        if(op == 1) {
            scanf("%d", &x);
            update(1, 1, n, l, r, x);
        } else printf("%d\n", query(1, 1, n, l, r));
    }
    return 0;
}