http://codeforces.com/contest/719/problem/E

题目大意：给你一串数组a，a[i]表示第i个斐波那契数列，有如下操作

①对[l,r]区间+一个val ②求出[l,r]区间的和。

定义区间的和为该区间内每个a[i]所对应的斐波那契数列的和。

 

思路：线段树保存区间val，和区间更新，用矩阵快速幂求解复杂度是m*logn*logk

 

//看看会不会爆int!数组会不会少了一维！//取物问题一定要小心先手胜利的条件#include 
      
       using namespace std;#define LL long long#define ALL(a) a.begin(), a.end()#define pb push_back#define mk make_pair#define fi first#define se second#define haha printf("haha\n")const int maxn = 1e5 + 5;const LL mod = 1e9 + 7;struct Node{    LL mat[2][2];    void reset(){memset(mat, 0, sizeof(mat));}    void getone(){        reset();        mat[0][0] = mat[1][1] = 1;    }};inline Node mul(Node A, Node B){    Node ans; ans.reset();    for (int i = 0; i < 2; i++)        for (int j = 0; j < 2; j++)            for (int k = 0; k < 2; k++)                ans.mat[i][j] = (ans.mat[i][j] + A.mat[i][k] * B.mat[k][j]) % mod;    return ans;}inline Node add(Node a, Node b){    Node ans; ans.reset();    for (int i = 0; i < 2; i++)        for (int j = 0; j < 2; j++)            ans.mat[i][j] = (a.mat[i][j] + b.mat[i][j]) % mod;    return ans;}inline Node kpow(LL k){    Node ans; ans.reset();    ans.mat[0][0] = ans.mat[1][1] = 1;    Node A;    A.mat[0][0] = A.mat[1][0] = A.mat[0][1] = 1;    A.mat[1][1] = 0;    while (k){        if (k & 1) ans = mul(ans, A);        A = mul(A, A);        k >>= 1;    }    return ans;}struct Mytree{    Node sum;    Node lazyk;}tree[maxn << 2];int n, m;inline void push_up(int o){    int lb = o << 1, rb = o << 1 | 1;    tree[o].sum = add(tree[lb].sum, tree[rb].sum);}void build_tree(int l, int r, int o){    if (l == r){        LL k; scanf("%lld", &k);        tree[o].sum = kpow(k);        tree[o].lazyk.getone();        return ;    }    tree[o].sum.reset(); tree[o].lazyk.getone();    int mid = (l + r) / 2;    if (l <= mid) build_tree(l, mid, o << 1);    if (r > mid) build_tree(mid + 1, r, o << 1 | 1);    push_up(o);}inline void push_down(int o){    int lb = o << 1, rb = o << 1 | 1;    tree[lb].sum = mul(tree[lb].sum, tree[o].lazyk);    tree[lb].lazyk = mul(tree[lb].lazyk, tree[o].lazyk);    tree[rb].sum = mul(tree[rb].sum, tree[o].lazyk);    tree[rb].lazyk = mul(tree[rb].lazyk, tree[o].lazyk);    tree[o].lazyk.getone();}void update(int l, int r, int ql, int qr, Node k, int o){    if (ql <= l && qr >= r){        tree[o].sum = mul(tree[o].sum, k);        tree[o].lazyk = mul(tree[o].lazyk, k);        return ;    }    int mid = (l + r) / 2;    push_down(o);    if (ql <= mid) update(l, mid, ql, qr, k, o << 1);    if (qr > mid) update(mid + 1, r, ql, qr, k, o << 1 | 1);    push_up(o);    return ;}Node query(int l, int r, int ql, int qr, int o){    if (ql <= l && qr >= r){        return tree[o].sum;    }    push_down(o);    Node ans; ans.reset();    int mid = (l + r) / 2;    if (ql <= mid) ans = add(query(l, mid, ql, qr, o << 1), ans);    if (qr > mid) ans = add(query(mid + 1, r, ql, qr, o << 1 | 1), ans);    push_up(o);    return ans;}int main(){    scanf("%d%d", &n, &m);    build_tree(1, n, 1);    for (int i = 0; i < m; i++){        int ty; scanf("%d", &ty);        if (ty == 1){            int l, r; LL k;            scanf("%d%d%lld", &l, &r, &k);            update(1, n, l, r, kpow(k), 1);        }        else if (ty == 2){            int l, r; scanf("%d%d", &l, &r);            Node ans = query(1, n, l, r, 1);            printf("%lld\n", ans.mat[1][0]);        }    }    return 0;}