有一个长度为n的正整数序列a（下标从1开始），共有m次操作，每次操作是如下2种操作中的一个：

1 l r x：将下标区间[l,r]内的所有ai都加上x。

2 l r：查询下标区间[l,r]内所有ai的斐波那契数列的第ai项的和，也就是 $f(a_l) + f(a_{l+1}) + … + f(a_r)$。 其中，$f(1) = f(2) = 1$，$f(i) = f(i-1) + f(i-2)$。

$n \le 100000, a_i \le 10^9, x \le 10^9$

感觉是线段树裸题，然后我直接上手拍了一个线段树板子加矩阵快速幂板子，自以为 $O(n\log n)$ 的时间复杂度稳过：

#include<bits/stdc++.h>
#define MOD 1004535809
#define MAXN 100010
#define lson 2 * now
#define rson 2 * now + 1
using namespace std;
typedef long long ll;
struct matrix{
    ll data[5][5];
    matrix operator * (const matrix b) const{
        matrix res;
        for(ll i = 1; i <= 2; i++){
            for(ll j = 1; j <= 2; j++){
                res.data[i][j] = 0;
            }
        }
        for(ll i = 1; i <= 2; i++){
            for(ll j = 1; j <= 2; j++){
                for(ll k = 1; k <= 2; k++){
                    res.data[i][j] += ( this->data[i][k] * b.data[k][j] ) % MOD;
                    res.data[i][j] %= MOD;
                }
            }
        }
        return res;
    }
    matrix operator + (const matrix b) const{
        matrix res;
        for(ll i = 1; i <= 2; i++){
            for(ll j = 1; j <= 2; j++){
                res.data[i][j] = 0;
            }
        }
        for(ll i = 1; i <= 2; i++){
            for(ll j = 1; j <= 2; j++){
                res.data[i][j] = (this->data[i][j] + b.data[i][j]) % MOD;
            }
        }
        return res;
    }
    void init(){
        memset(data, 0, sizeof(data));
        for(ll i = 1; i <= 2; i++) data[i][i] = 1;
    }
    void print(){
        for(int i = 1; i <= 2; i++){
            for(int j = 1; j <= 2; j++){
                printf("%lld ",data[i][j]);
            }
            printf("\n");
        }
    }
};
struct node{
    int l, r;
    int lazy_tag;
    matrix res;
};
matrix a, b, tmp;
node tree[MAXN << 2];
int n, m;
int num[MAXN];
matrix matrix_power(matrix mat,ll exp){
    matrix res;
    res.init();
    while(exp){
        if(exp & 1) res = res * mat;
        mat = mat * mat;
        exp >>= 1;
    }
    return res;
}
void push_up(int now){
    tree[now].res = tree[lson].res + tree[rson].res;
}
void push_down(int now){
    if(tree[now].lazy_tag){
        tree[lson].lazy_tag += tree[now].lazy_tag;
        tree[rson].lazy_tag += tree[now].lazy_tag;
        tree[lson].res = matrix_power(a, tree[now].lazy_tag) * tree[lson].res;
        tree[rson].res = matrix_power(a, tree[now].lazy_tag) * tree[rson].res;
        tree[now].lazy_tag = 0;
    }
}
void build(int now, int l, int r){
    tree[now].l = l; tree[now].r = r;
    if(tree[now].l == tree[now].r){
        tree[now].lazy_tag = 0;
        matrix tmp = matrix_power(a, num[l] - 1);
        tree[now].res = tmp * b;
        return ;
    }
    int mid = (tree[now].l + tree[now].r) >> 1;
    build(lson, l, mid); build(rson, mid + 1, r);
    push_up(now);
}
void update(int now, int l, int r, int x){
    if(tree[now].l >= l && tree[now].r <= r){
        tree[now].lazy_tag += x;
        tree[now].res = tmp * tree[now].res;
        return ;
    }
    push_down(now);
    int mid = (tree[now].l + tree[now].r) >> 1;
    if(r <= mid) update(lson, l, r, x);
    else if(l > mid) update(rson, l, r, x);
    else update(lson, l, mid, x), update(rson, mid + 1, r, x);
    push_up(now);
}
ll query(int now, int l, int r){
    if(tree[now].l >= l && tree[now].r <= r){
        return tree[now].res.data[1][1];
    }
    push_down(now);
    int mid = (tree[now].l + tree[now].r) >> 1;
    if(r <= mid) return query(lson, l, r);
    else if(l > mid) return query(rson, l, r);
    else return (query(lson, l, mid) + query(rson, mid + 1, r)) % MOD;
}
int main(){
    // freopen("fib.in","r",stdin);
    // freopen("fib.out","w",stdout);
    a.data[1][1] = 1; a.data[1][2] = 1; a.data[2][1] = 1; a.data[2][2] = 0;
    b.data[1][1] = 1; b.data[1][2] = 0; b.data[2][1] = 0; b.data[2][2] = 0;
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++) scanf("%d",&num[i]);
    build(1, 1, n);
    for(int i = 1; i <= m; i++){
        int op, l, r, x;
        scanf("%d",&op);
        if(op == 1){
            scanf("%d%d%d",&l,&r,&x);
            tmp = matrix_power(a, x);
            update(1, l, r, x);
        }else if(op == 2){
            scanf("%d%d",&l,&r);
            printf("%lld\n",query(1, l, r));
        }
    }
    return 0;
}

然后就 T 飞。

但是我觉得时间复杂度是正确的。