题目连接：E. Sasha and Array
题意：给一个数组，两种操作，第一种给区间[l,r]的值都加上x,第二种求区间[l,r],每一项对应的fib数之和，
题解：第一种操作很好解决用个线段树加个laz标记就可以了，但是求和就不好做了，我们求某一项的fib数可以用矩阵快速幂求出。所以我们把线段树的每一个node有看成矩阵，所以对某一区间加x,就是把这区间的每个矩阵都乘矩阵{0，1；1，1；}的x次幂；把laz也换成矩阵，然后其他操作就是裸的线段树。
参考博客：https://www.cnblogs.com/qscqesze/p/5902547.html
1 #include<bits/stdc++.h> 2 #include<set> 3 #include<cstdio> 4 #include<iomanip> 5 #include<iostream> 6 #include<string> 7 #include<cstring> 8 #include<algorithm> 9 #define pb push_back 10 #define mk make_pair 11 #define ll long long 12 #define fi first 13 #define se second 14 #define PI 3.14159265 15 #define ls l,m,rt<<1 16 #define rs m+1,r,rt<<1|1 17 #define eps 1e-7 18 #define pii pair<int,int> 19 typedef unsigned long long ull; 20 const int mod=1e9+7; 21 const ll inf=0x3f3f3f3f3f3f3f; 22 const int maxn=1e5+5; 23 using namespace std; 24 struct mat 25 { 26 int n, m; 27 ll a[2][2]; 28 mat() {} 29 void init(int _n, int _m) 30 { 31 n = _n; 32 m = _m; 33 for(int i = 0; i < n; i++) 34 { 35 for(int j = 0; j < m; j++) a[i][j] = 0; 36 } 37 } 38 void one() 39 { 40 init(2,2);a[0][0]=1;a[1][1]=1; 41 } 42 mat operator + (const mat &B)const 43 { 44 mat C; 45 C.init(n,m); 46 for(int i=0; i<n; i++) 47 for(int j=0; j<m; j++) 48 C.a[i][j]=(a[i][j]+B.a[i][j])%mod; 49 return C; 50 } 51 mat operator*(const mat &P)const 52 { 53 mat ret; 54 ret.init(n,m); 55 for(int i = 0; i < n; i++) 56 { 57 for(int k = 0; k < m; k++) 58 { 59 if(a[i][k]) 60 { 61 for(int j = 0; j < P.m; j++) 62 { 63 ret.a[i][j] = ((ll)a[i][k] * P.a[k][j] + ret.a[i][j]) % mod; 64 } 65 } 66 } 67 } 68 return ret; 69 } 70 mat operator^(const ll &P)const 71 { 72 ll num = P; 73 mat ret, tmp = *this; 74 ret.init(n,m); 75 for(int i = 0; i < n; i++) ret.a[i][i] = 1; 76 while(num) 77 { 78 if(num & 1) ret = ret * tmp; 79 tmp = tmp * tmp; 80 num >>= 1; 81 } 82 return ret; 83 } 84 }; 85 ll a[maxn];int n,m; 86 mat sum[maxn<<2],laz[maxn<<2]; 87 bool flag[maxn<<2]; 88 void push_up(int rt) 89 { 90 sum[rt]=sum[rt<<1]+sum[rt<<1|1]; 91 } 92 void built(int l,int r,int rt) 93 { sum[rt].init(2,2);laz[rt].one();flag[rt]=0; 94 if(l==r) 95 { 96 mat t;t.init(2,2);t.a[0][0]=0;t.a[0][1]=1;t.a[1][1]=1;t.a[1][0]=1; 97 sum[rt]=t^a[l];return ; 98 } 99 int m=(l+r)>>1; 100 built(ls);built(rs); 101 push_up(rt); 102 } 103 void push_down(int rt) 104 { 105 if(flag[rt]) 106 { 107 sum[rt<<1]=sum[rt<<1]*laz[rt]; 108 laz[rt<<1]=laz[rt<<1]*laz[rt]; 109 sum[rt<<1|1]=sum[rt<<1|1]*laz[rt]; 110 laz[rt<<1|1]=laz[rt<<1|1]*laz[rt]; 111 flag[rt<<1]=flag[rt<<1|1]=1; 112 laz[rt].one(); 113 flag[rt]=0; 114 } 115 } 116 void update(int L,int R,mat v,int l,int r,int rt) 117 { 118 if(L<=l&&r<=R) 119 { 120 laz[rt]=laz[rt]*v; 121 sum[rt]=sum[rt]*v; 122 flag[rt]=1; 123 return ; 124 } 125 push_down(rt); 126 int m=(l+r)>>1; 127 if(L<=m)update(L,R,v,ls); 128 if(R>m)update(L,R,v,rs); 129 push_up(rt); 130 } 131 mat query(int L,int R,int l,int r,int rt) 132 { 133 if(L<=l&&r<=R) return sum[rt]; 134 push_down(rt); 135 int m=(l+r)>>1; 136 mat ans;ans.init(2,2); 137 if(L<=m)ans=ans+query(L,R,ls); 138 if(R>m)ans=ans+query(L,R,rs); 139 push_up(rt); 140 return ans; 141 } 142 int main() 143 { 144 scanf("%d %d",&n,&m); 145 for(int i=1;i<=n;i++)scanf("%d",a+i); 146 built(1,n,1); 147 while(m--) 148 { 149 int op,l,r,v; 150 scanf("%d",&op); 151 if(op==2) 152 { 153 scanf("%d %d",&l,&r); 154 printf("%lld ",query(l,r,1,n,1).a[1][0]); 155 } 156 else 157 { 158 scanf("%d %d %d",&l,&r,&v); 159 mat t;t.init(2,2);t.a[0][0]=0;t.a[0][1]=1;t.a[1][1]=1;t.a[1][0]=1; 160 t=t^v; 161 update(l,r,t,1,n,1); 162 } 163 164 } 165 return 0; 166 }