题目id：4306
题意
给定长度为 n 的序列 a 要求支持 m 次操作：
opt_1 ：给定 fr_i , to_i , val_i,\forall i \in [fr_i , to_i] , a_i = a_i + val_i
opt_2 ：给定 fr_i , to_i 求 \sum\limits_{i=fr_i}^{to_i} f(a_i) 对 10^9+7 取模后的结果
其中 f(i) 表示斐波那契数列第 i 项，
f(i) = \left\{\begin{aligned} 1 \space (n \le 2) \\ f(n-1)+f(n-2) \space (n\ge 3) \end{aligned}\right.
数据范围
n,m \leq 100000
思路
发现题目要求区间操作，考虑线段树维护
对于斐波那契数列，显然地可以构造矩阵转移
\begin{vmatrix} f(i) & f(i-1) \end{vmatrix} \times \begin{vmatrix} 1 & 1 \\ 1 & 0 \end{vmatrix} = \begin{vmatrix} f(i+1) & f(i) \end{vmatrix}
用线段树+矩阵快速幂维护即可
细节
初始化线段树时，对值为 1 的结点都置为 \begin{vmatrix}1&0\end{vmatrix} ，其他节点赋值为 \begin{vmatrix} 1 & 1 \end{vmatrix} \times \begin{vmatrix} 1 & 1 \\ 1 & 0 \end{vmatrix} ^{n-2}
由于这道题的出题人极其可恶的卡常，对于矩阵乘法和加法要循环展开，加上快读快输
code
#include<bits/stdc++.h>
using namespace std;
#define mod(a) a>1000000007?a-1000000007:a
static inline char Get_Char()
{
static char buffer[100000],*S=buffer,*T=buffer;
return (S==T&&(T=(S=buffer)+fread(buffer,1,100000,stdin),S==T)?EOF:*S++);
}
inline int read()
{
int res=0,flag=1;
char ch=Get_Char();
while(!isalnum(ch)) (ch=='-')?flag=-1:1,ch=Get_Char();
while(isalnum(ch)) res=res*10+ch-'0',ch=Get_Char();
return res*flag;
}
inline void write(int x)
{
char buf[20]; int len=0;
if(x<=0) putchar((x==0)?'0':'-'); x=abs(x);
while(x!=0) buf[++len]=x%10+'0',x/=10;
while(len!=0) putchar(buf[len--]);
putchar('\n');
}
const int mod=1e9+7;
struct matrix
{
int val[2][2];
void Set()
{
val[0][0]=val[1][1]=1;
val[0][1]=val[1][0]=0;
return ;
}
struct matrix operator *(const struct matrix &other)const
{
struct matrix res;
res.val[0][0]=mod((long long)this->val[0][0]*other.val[0][0]%mod+(long long)this->val[0][1]*other.val[1][0]%mod);
res.val[1][0]=mod((long long)this->val[1][0]*other.val[0][0]%mod+(long long)this->val[1][1]*other.val[1][0]%mod);
res.val[0][1]=mod((long long)this->val[0][0]*other.val[0][1]%mod+(long long)this->val[0][1]*other.val[1][1]%mod);
res.val[1][1]=mod((long long)this->val[1][0]*other.val[0][1]%mod+(long long)this->val[1][1]*other.val[1][1]%mod);
return res;
}
struct matrix operator +(const struct matrix &other)const
{
struct matrix res;
res.val[0][0]=mod(this->val[0][0]+other.val[0][0]);
res.val[0][1]=mod(this->val[0][1]+other.val[0][1]);
res.val[1][0]=mod(this->val[1][0]+other.val[1][0]);
res.val[1][1]=mod(this->val[1][1]+other.val[1][1]);
return res;
}
/*
void print()
{
for(int i=0;i<=1;i++)
{
for(int j=0;j<=1;j++)
cout<<val[i][j]<<" ";
cout<<endl;
}
return ;
}*/
};
struct node
{
struct matrix data,tag;
};
struct matrix base[50];
struct node nd[400010];
int val[100010];
struct matrix quick(int p)//a=f(now+p)
{
struct matrix res;
res.Set();
for(int i=1;i<=46&&p!=0;i++)
{
if(p&1)
res=res*base[i];
p>>=1;
}
return res;
}
void pushdown(int id)
{
nd[id<<1].tag=nd[id<<1].tag*nd[id].tag;
nd[id<<1|1].tag=nd[id<<1|1].tag*nd[id].tag;
nd[id<<1].data=nd[id<<1].data*nd[id].tag;
nd[id<<1|1].data=nd[id<<1|1].data*nd[id].tag;
nd[id].tag.Set();
return ;
}
void pushup(int id)
{
// nd[id].sum=(nd[id<<1].sum+nd[id<<1|1].sum)%mod;
nd[id].data=nd[id<<1].data+nd[id<<1|1].data;
return ;
}
void build(int left,int right,int id)
{
nd[id].tag.Set();
if(left==right)
{
if(val[left]==1)
nd[id].data.val[0][0]=1;
else
nd[id].data.val[0][0]=nd[id].data.val[0][1]=1;
if(val[left]>2)
nd[id].data=nd[id].data*quick(val[left]-2);
return ;
}
int mid=(left+right)>>1;
build(left,mid,id<<1);
build(mid+1,right,id<<1|1);
pushup(id);
return ;
}
void modify(int left,int right,int id,int start,int end,int value)
{
if(right<start||end<left)
return ;
if(start<=left&&right<=end)
{
struct matrix tmp=quick(value);
nd[id].data=nd[id].data*tmp;
nd[id].tag=nd[id].tag*tmp;
return ;
}
int mid=(left+right)>>1;
pushdown(id);
modify(left,mid,id<<1,start,end,value);
modify(mid+1,right,id<<1|1,start,end,value);
pushup(id);
return ;
}
int query(int left,int right,int id,int start,int end)
{
if(right<start||end<left)
return 0;
if(start<=left&&right<=end)
return mod(nd[id].data.val[0][0]);
int mid=(left+right)>>1;
pushdown(id);
int ansl=query(left,mid,id<<1,start,end);
int ansr=query(mid+1,right,id<<1|1,start,end);
return mod(ansl+ansr);
}
int main(int argc,const char *argv[])
{
base[1].val[0][0]=base[1].val[0][1]=base[1].val[1][0]=1;
int n=read(),q=read();
for(int i=2;i<=46;i++)
base[i]=base[i-1]*base[i-1];
for(int i=1;i<=n;i++)
val[i]=read();
build(1,n,1);
for(int i=1;i<=q;i++)
{
int opt=read(),l=read(),r=read();
if(opt==1)
{
int value=read();
modify(1,n,1,l,r,value);
}
if(opt==2)
write(query(1,n,1,l,r));
}
return 0;
}
