/* 题意：给定一个长度为n的序列a。 两种操作： 1.给定区间l r 加上某个数x. 2.查询区间l r sigma(fib(ai)) fib代表斐波那契数列。 思路： 1.矩阵操作，由矩阵快速幂求一个fib数根据矩阵的乘法结合率，A*C+B*C=(A+B)*C; 这样可以通过线段树维护某个区间2*1矩阵的和。 2.时限卡的紧...用我的矩阵乘法板子TLE了。所以把板子里边的三重循环改成手工公式... 3.注意(a+b)%mod。这种，改成if(a+b>=mod)a+b-mod这种形式时间几乎减半了==...（因为查询和更新操作每次都要把两个矩阵加起来...所以这种优化在这题来说作用明显） 4.注意lazy标记不要记录要乘多矩阵多少次方...而是直接记录该矩阵...这是最重要的一个优化（个人认为）.因为每次向下层更新都要求一次矩阵... */ #include<bits/stdc++.h> #define N 100020 #define MAXS 2 using namespace std; long long jilu[N]; long long jil[N]; long long MOD =1e9+7; struct Matrix { long long mx[MAXS][MAXS]; Matrix() { memset(mx,0,sizeof(mx)); } Matrix operator* (const Matrix& b) const { Matrix tmp; tmp.mx[0][0]=mx[0][0]*b.mx[0][0]+mx[0][1]*b.mx[1][0]; if(tmp.mx[0][0]>=MOD)tmp.mx[0][0]%=MOD; tmp.mx[0][1]=mx[0][0]*b.mx[0][1]+mx[0][1]*b.mx[1][1]; if(tmp.mx[0][1]>=MOD)tmp.mx[0][1]%=MOD; tmp.mx[1][0]=mx[1][0]*b.mx[0][0]+mx[1][1]*b.mx[1][0]; if(tmp.mx[1][0]>=MOD)tmp.mx[1][0]%=MOD; tmp.mx[1][1]=mx[1][0]*b.mx[0][1]+mx[1][1]*b.mx[1][1]; if(tmp.mx[1][1]>=MOD)tmp.mx[1][1]%=MOD; return tmp; } Matrix operator +(const Matrix &b)const{ Matrix tmp; for(int i=0;i<2;i++){ for(int j=0;j<2;j++){ tmp.mx[i][j]=(mx[i][j]+b.mx[i][j]); if(tmp.mx[i][j]>=MOD)tmp.mx[i][j]-=MOD; } } return tmp; } void initE() { memset(mx,0, sizeof(mx)); for (int i=0 ; i<2 ; i++) { mx[i][i]=1; } } Matrix mpow(long long k) { Matrix c,b; c=(*this); b.initE(); while(k) { if(k&1) { b=b*c; } c=c*c; k>>=1; } return b; } }; Matrix biao,ben; struct tr{ Matrix val,tt; long long aa; int s,e; }; tr tree[100050<<2]; void build(int s,int e,int k){ tr &tmp=tree[k]; tmp.s=s;tmp.e=e;tmp.aa=0; tmp.tt.initE(); if(s==e){ tmp.val.mx[0][0]=jilu[s]; tmp.val.mx[1][0]=jil[s]; return; } int mid=(s+e)>>1; build(s,mid,k<<1); build(mid+1,e,k<<1|1); tmp.val=tree[k<<1].val+tree[k<<1|1].val; } void add(int s,int e,int k,int num){ tr &tmp=tree[k]; if(s==tmp.s&&e==tmp.e){ Matrix ttt=biao.mpow(num); tmp.tt=ttt*tmp.tt; tmp.val=ttt*tmp.val; tmp.aa+=num; return; } if(tmp.aa){ tree[k<<1].aa+=tmp.aa; tree[k<<1].val=tmp.tt*tree[k<<1].val; tree[k<<1].tt=tmp.tt*tree[k<<1].tt; tree[k<<1|1].aa+=tmp.aa; tree[k<<1|1].val=tmp.tt*tree[k<<1|1].val; tree[k<<1|1].tt=tmp.tt*tree[k<<1|1].tt; tmp.tt.initE(); tmp.aa=0; } int mid=(tmp.s+tmp.e)>>1; if(e<=mid)add(s,e,k<<1,num); else if(s>mid)add(s,e,k<<1|1,num); else{ add(s,mid,k<<1,num); add(mid+1,e,k<<1|1,num); } tmp.val=tree[k<<1].val+tree[k<<1|1].val; } long long query(int s,int e,int k){ tr &tmp=tree[k]; if(tmp.s==s&&tmp.e==e){ return tmp.val.mx[0][0]; } if(tmp.aa){ tree[k<<1].aa+=tmp.aa; tree[k<<1].val=tmp.tt*tree[k<<1].val; tree[k<<1].tt=tmp.tt*tree[k<<1].tt; tree[k<<1|1].aa+=tmp.aa; tree[k<<1|1].val=tmp.tt*tree[k<<1|1].val; tree[k<<1|1].tt=tmp.tt*tree[k<<1|1].tt; tmp.tt.initE(); tmp.aa=0; } int mid=(tmp.s+tmp.e)>>1; if(e<=mid)return query(s,e,k<<1); else if(s>mid)return query(s,e,k<<1|1); else return (query(s,mid,k<<1)+query(mid+1,e,k<<1|1))%MOD; } int main() { int n,m; biao.mx[0][0]=biao.mx[0][1]=biao.mx[1][0]=1; ben.mx[1][0]=ben.mx[0][0]=1; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%lld",jilu+i); if(jilu[i]==1){ jil[i]=0; } else if(jilu[i]==2){ jilu[i]=1; jil[i]=1; } else{ Matrix rel=biao.mpow(jilu[i]-2)*ben; jilu[i]=rel.mx[0][0]; jil[i]=rel.mx[1][0]; } } build(1,n,1); for(int i=1;i<=m;i++){ int typ,l,r,x; scanf("%d",&typ); if(typ==1){ scanf("%d%d%d",&l,&r,&x); add(l,r,1,x); } else{ scanf("%d%d",&l,&r); printf("%lld ",query(l,r,1)); } } }