提高培优班D2T4线段树题解
题目id：4306
题意简述
给定一个序列 a ，维护区间加，区间求 \Sigma_{i=1}^{n}f(a_i)\ mod\ (1\times10^9+7) 。
f(a_i) 表示第 a_i 个斐波那契数列的值，特别的，$f(1)=1\ ,\ f(2)=1$ 。
n,m\le1\times10^5 ，保证输入为 \le1\times10^9 的正整数。
思路
看到斐波那契数列，那肯定会想到其通项计算公式和矩阵快速幂计算。
因为矩阵快速幂常数大，所以我是先试试通项计算公式的，然后忘了通向是啥了，就只能现推。
对于 f_n=f_{n-1}+f_{n-2} ，其形式接近等比数列 ，于是我们假设 f_n=A*q^{n} ，
可以得到：$Aq^n=Aq^{n-1}+A*q^{n-2}$
移项得：$q^2-q-1=0$
\therefore q=\frac{1\pm\sqrt{5}}{2}
\therefore f_n=A*(\frac{1+\sqrt{5}}{2})^n+B*(\frac{1-\sqrt{5}}{2})^n
代入 f_1\ ,\ f_2 得：$f_n=\frac{(\frac{1+\sqrt5}{2})^n-(\frac{1-\sqrt5}{2})^n}{\sqrt{5}}$
发现，我们并不能对它做跟区间有关的操作。推了个寂寞
那么，就只剩下，矩阵快速幂了，我们令计算矩阵为 g 。
注意到，对于 f_{a_i} \rightarrow f_{a_i+x} 的转移，其实就是 f_{a_i} 所对应的矩阵 \times g^x 。
那么问题就很简单了，所谓的区间加，其实是区间乘，然后维护区间和即可。
显然，线段树、分块等都可以写，主要是一些细节问题，这里主要讲线段树，我才不会说我分块写炸了。
首先， a_i 直接变成所对应的矩阵，因为矩阵满足分配律和结合律，所以上推的时候直接进行矩阵加法即可。
然后对于区间加 x ，直接把它变成 g^x ，然后做区间乘法。
最后，你可以试试重载运算符，这样相当于，打了个矩阵模板，然后打了个线段树模板，就过了。
时间复杂度 \Theta(n\log n) 。
code
#define lp (p<<1)
#define rp (p<<1|1)
int n,m,a[N];
class node{
public:
int g[2][2];
inline void re(){
g[0][0]=g[0][1]=g[1][0]=1,g[1][1]=0;//计算矩阵
}
inline void rr(){
g[0][0]=g[1][1]=1;g[0][1]=g[1][0]=0;//单位矩阵
}
friend node operator *(node x,node y);
friend node operator +(node x,node y);
};
node operator *(node x,node y){
node z;
z.g[0][0]=(1ll*x.g[0][0]*y.g[0][0]%mod+1ll*x.g[0][1]*y.g[1][0]%mod)%mod;z.g[0][1]=(1ll*x.g[0][0]*y.g[0][1]%mod+1ll*x.g[0][1]*y.g[1][1]%mod)%mod;
z.g[1][0]=(1ll*x.g[1][0]*y.g[0][0]%mod+1ll*x.g[1][1]*y.g[1][0]%mod)%mod;z.g[1][1]=(1ll*x.g[1][0]*y.g[0][1]%mod+1ll*x.g[1][1]*y.g[1][1]%mod)%mod;
return z;
}
node operator +(node x,node y){
node z;
z.g[0][0]=(x.g[0][0]+y.g[0][0])%mod;z.g[0][1]=(x.g[0][1]+y.g[0][1])%mod;
z.g[1][0]=(x.g[1][0]+y.g[1][0])%mod;z.g[1][1]=(x.g[1][1]+y.g[1][1])%mod;
return z;
}
inline node qpow(int y){
node A,B;A.rr();B.re();
for(;y;y>>=1,B=B*B) if(y&1) A=A*B;
return A;
}
struct segmentree{node v;node mul;}e[N<<2];
void build(int p,int l,int r){
e[p].mul.rr();
if(l==r)
e[p].v=qpow(a[l]-1);
else {
int mid=l+r>>1;build(lp,l,mid);build(rp,mid+1,r);
e[p].v=(e[lp].v+e[rp].v);
}
}
void spread(int p){
e[lp].v=(e[lp].v*e[p].mul);
e[rp].v=(e[rp].v*e[p].mul);
e[lp].mul=(e[lp].mul*e[p].mul);
e[rp].mul=(e[rp].mul*e[p].mul);
e[p].mul.rr();
}
void upd(int p,int l,int r,int L,int R,int k){
// printf("p:%d l:%d r:%d val:%d mul: %d\n",p,l,r,e[p].v.g[0][1],e[p].mul);
if(l>R||r<L)return ;
if(L<=l&&R>=r){
e[p].v=e[p].v*qpow(k);
e[p].mul=(e[p].mul*qpow(k));
return ;
}
spread(p);
int mid=l+r>>1;
if(mid>=L)upd(lp,l,mid,L,R,k);
if(mid<R)upd(rp,mid+1,r,L,R,k);
e[p].v=(e[lp].v+e[rp].v);
return;
}
int ask(int p,int l,int r,int L,int R){
// printf("p:%d l:%d r:%d val:%d mul: %d\n",p,l,r,e[p].v.g[0][1],e[p].mul);
if(L<=l&&R>=r){
// printf("<p:%d l:%d r:%d val:%d mul: %d>\n",p,l,r,e[p].v.g[0][1],e[p].mul);
return e[p].v.g[0][0];
}
spread(p);
int ret=0;
int mid=l+r>>1;
if(mid>=L)ret=(ret+ask(lp,l,mid,L,R))%mod;
if(mid<R)ret=(ret+ask(rp,mid+1,r,L,R))%mod;
//printf("[%d %d] : %d right : %d\n", l, r, ret, ask(rp, mid + 1, r, L, R));
return ret;
}
signed main(){
read(n,m);
for(int i=1;i<=n;i++) read(a[i]);
build(1,1,n);
int opt,l,r,x;
while(m--){
read(opt,l,r);
if(opt==1) read(x),upd(1,1,n,l,r,x);
else printf("%lld\n",ask(1,1,n,l,r));
}
return 0;
}