Codeforces

Luogu

分析

考虑怎么用矩阵求出斐波那契数列的。有
$$
\begin{bmatrix}1&0\end{bmatrix}\times\begin{bmatrix}1&1\\1&0\end{bmatrix}^{n-1}=\begin{bmatrix}f_n&f_{n-1}\end{bmatrix}
$$
为了方便，下面设 $Q=\begin{bmatrix}1&1\\1&0\end{bmatrix}$ 。

考虑使用线段树维护。每个叶子节点维护一个矩阵：若该位置的值为 $i$ ，则维护的矩阵为 $Q^{i-1}$ 。

注意到矩阵乘法是满足分配律的，那么我们只需要求 $[l,r]$ 内所有维护的矩阵的和，再乘上 $\begin{bmatrix}1&0\end{bmatrix}$ 就可以得到答案了。这个可以简单的通过维护区间和来解决。

现在考虑如何修改。每次把 $[l,r]$ 内的数加 $x$ 就相当于把 $[l,r]$ 内维护的矩阵乘上了 $Q^x$ ，直接打区间乘法标记即可。

初始化把叶节点的矩阵设为 $Q^{a_i-1}$ 即可。

别的好像没什么好说的了，可以结合代码理解一下。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000;
const int mod=1e9+7;

struct Matrix {
    int s[2][2];
    Matrix() { s[0][0]=s[0][1]=s[1][0]=s[1][1]=0; }
    int* operator [](int i) { return s[i]; }
} P,Q,I;
Matrix operator +(Matrix a,Matrix b) { Matrix c;
    for (re int i=0;i<2;++i)
        for (re int j=0;j<2;++j)
            c[i][j]=(a[i][j]+b[i][j])%mod;
    return c;
}
Matrix operator *(Matrix a,Matrix b) { Matrix c;
    for (re int i=0;i<2;++i)
        for (re int k=0;k<2;++k)
            for (re int j=0;j<2;++j)
                c[i][j]=(c[i][j]+1ll*a[i][k]*b[k][j])%mod;
    return c;
}
bool operator !=(Matrix a,Matrix b) {
    for (re int i=0;i<2;++i)
        for (re int j=0;j<2;++j)
            if (a[i][j]!=b[i][j]) return true;
    return false;
}
inline Matrix qpow(Matrix a,int b) { Matrix c=I;
    for (;b;b>>=1,a=a*a) if (b&1) c=c*a;
    return c;
}
inline void init_Matrix() {
    P[0][0]=1,P[0][1]=P[1][0]=P[1][1]=0;
    Q[0][0]=Q[0][1]=Q[1][0]=1,Q[1][1]=0;
    I[0][0]=I[1][1]=1,I[0][1]=I[1][0]=0;
}

#define ls (o<<1)
#define rs (o<<1|1)
Matrix sumv[N<<2],mulv[N<<2];
inline void update(int o,Matrix A) {
    sumv[o]=sumv[o]*A,mulv[o]=mulv[o]*A;
}    
inline void pushup(int o) { sumv[o]=sumv[ls]+sumv[rs]; }
inline void pushdown(int o) {
    if (mulv[o]!=I) {
        update(ls,mulv[o]),update(rs,mulv[o]);
        mulv[o]=I;
    }
}
inline void build(int o,int l,int r) {
    mulv[o]=I;
    if (l==r) { sumv[o]=qpow(Q,read()-1); return; }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(o);
}
inline void modify(int o,int l,int r,int ql,int qr,Matrix w) {
    if (ql<=l&&r<=qr) { update(o,w); return; }
    int mid=(l+r)>>1; pushdown(o);
    if (ql<=mid) modify(ls,l,mid,ql,qr,w);
    if (qr>mid) modify(rs,mid+1,r,ql,qr,w);
    pushup(o);
}
inline Matrix query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return sumv[o];
    int mid=(l+r)>>1; Matrix res; pushdown(o);
    if (ql<=mid) res=res+query(ls,l,mid,ql,qr);
    if (qr>mid) res=res+query(rs,mid+1,r,ql,qr);
    pushup(o); return res;
}
#undef ls
#undef rs

int main() { init_Matrix();
    int n=read(),m=read();
    build(1,1,n);
    while (m--) {
        int op=read(),l=read(),r=read();
        if (op==1) { int x=read(); modify(1,1,n,l,r,qpow(Q,x)); }
        else printf("%d\n",(P*query(1,1,n,l,r))[0][0]);
    }
    return 0;
}