线段树维护矩阵。
本以为会调不知道多长时间，结果不到 50 mins 就完成了。
初始想法是维护原序列，在求值的时候再求斐波那契数。但是感觉跑的慢。
然后决定维护斐波那契数列（非矩阵），但是发现每次 update 时构造新矩阵比较麻烦。
最后才想到把矩阵当成点来维护。
测完跑了 1.1min，看了下题解区发现思路也差不太多？
Solution
我们在每个点维护 (egin{bmatrix} f_i & f_{i-1} \ end{bmatrix}) 这样一个矩阵。
对于建树，我们直接矩阵快速幂处理出当前 (f_{a_i}) 所在的矩阵即可。
对于取和操作，和维护整数时一样，每次统计矩阵 sum.z[1][1] 的值即可。
剩下的操作才是重点。
对于修改操作，在原数列上是 (a_i o a_i +k)，换到斐波那契数就是 (f_{a_i} o f_{a_i+k})，也就是向后移 (k) 项。
根据矩阵求斐波那契数列的式子，我们在当前点维护的矩阵上乘一个 (egin{bmatrix} 1 & 1 \ 1 & 0 end{bmatrix}^{k-1}) 即可。而这个矩阵用矩阵快速幂现求即可。
对于节点信息的上传和懒标记的下传，我们直接相加。下传的懒标记就是上面的 (k-1) 次方矩阵。
因为矩阵的乘法满足分配律，所以我们先将矩阵相加再相乘对答案无影响。
至于重载加法乘法运算符什么的就不赘述了。
几个问题
-
注意取模并开
long long。 -
注意每次矩阵快速幂时要将 (egin{bmatrix} 1 & 1 \ 1 & 0 end{bmatrix}) 这个矩阵重置。
-
注意懒标记初始是单位矩阵而不是零矩阵。
-
建树时记得特判一下 (a[i]=1 exttt{or} 2) 的情况。
Code
写的比较丑，大家将就看吧。
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 400010
#define INF 0x3f3f3f3f
#define Mod 1000000007
#define int long long
using namespace std;
int n,m,a[maxn];
int read(){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
return s*w;
}
struct Matrix{
int z[4][4];
Matrix(){memset(z,0,sizeof z);}
Matrix operator * (const Matrix &b) const{
Matrix res;
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
for(int k=1;k<=2;k++)
res.z[i][k]=(res.z[i][k]+z[i][j]*b.z[j][k])%Mod;
return res;
}
Matrix operator + (const Matrix &b) const{
Matrix res;
res.z[1][1]=(z[1][1]+b.z[1][1])%Mod;
res.z[1][2]=(z[1][2]+b.z[1][2])%Mod;
res.z[2][1]=(z[2][1]+b.z[2][1])%Mod;
res.z[2][2]=(z[2][2]+b.z[2][2])%Mod;
return res;
}
}ans,X;
Matrix quickpow(Matrix Now,int y){
while(y){
if(y&1) Now=Now*X;
X=X*X;y>>=1;
}
return Now;
}
namespace Seg{
#define ls x<<1
#define rs x<<1|1
Matrix sum[maxn],lazy[maxn];
void pushup(int x){
sum[x]=sum[ls]+sum[rs];
}
void pushdown(int x){
if(lazy[x].z[1][1]==1&&lazy[x].z[2][2]==1&&!lazy[x].z[1][2]&&!lazy[x].z[2][1]) return;
sum[ls]=sum[ls]*lazy[x];sum[rs]=sum[rs]*lazy[x];
lazy[ls]=lazy[ls]*lazy[x];lazy[rs]=lazy[rs]*lazy[x];
lazy[x].z[1][1]=lazy[x].z[2][2]=1;lazy[x].z[1][2]=lazy[x].z[2][1]=0;
}
void build(int x,int l,int r){
lazy[x].z[1][1]=lazy[x].z[2][2]=1;
if(l==r){
X.z[2][2]=0;
ans.z[1][1]=ans.z[1][2]=1;
X.z[1][1]=X.z[1][2]=X.z[2][1]=1;
if(a[l]==1) sum[x].z[1][1]=1;
else if(a[l]==2) sum[x].z[1][1]=sum[x].z[1][2]=1;
else sum[x]=quickpow(ans,a[l]-2);
return;
}
int mid=l+r>>1;
build(ls,l,mid);build(rs,mid+1,r);
pushup(x);
}
void update(int x,int l,int r,int L,int R,Matrix k){
if(L<=l&&R>=r){
sum[x]=sum[x]*k;
lazy[x]=lazy[x]*k;
return;
}
int mid=l+r>>1;pushdown(x);
if(L<=mid) update(ls,l,mid,L,R,k);
if(R>=mid+1) update(rs,mid+1,r,L,R,k);
pushup(x);
}
int query(int x,int l,int r,int L,int R){
int ans=0;
if(L<=l&&R>=r)
return sum[x].z[1][1]%Mod;
int mid=l+r>>1;pushdown(x);
if(L<=mid) ans=(ans+query(ls,l,mid,L,R))%Mod;
if(R>=mid+1) ans=(ans+query(rs,mid+1,r,L,R))%Mod;
return ans;
}
}
signed main(){
n=read();m=read();
for(int i=1;i<=n;i++) a[i]=read();
Seg::build(1,1,n);
for(int i=1,opt,x,y,k;i<=m;i++){
opt=read();x=read();y=read();
if(opt==1){
k=read();X.z[2][2]=0;
X.z[1][1]=X.z[1][2]=X.z[2][1]=1;
Matrix Base=quickpow(X,k-1);
Seg::update(1,1,n,x,y,Base);
}
else printf("%lld
",Seg::query(1,1,n,x,y)%Mod);
}
return 0;
}