有两个操作：
- 将 $[l,r]$所有数 + $x$
- 求 $\sum_{i=l}^{r}fib(i)$
$n=m=10^5$
直接求不好求，改成矩阵乘法的形式：
$a_{i}=M^x\times fib_{1}$
直接用线段树维护 $M^x$ 即可.
因为矩阵乘法是满足结合律的： $A*B+A*C=A*(B+C)$
$a_{i}=M^x\times fib_{1}$
直接用线段树维护 $M^x$ 即可.
因为矩阵乘法是满足结合律的： $A*B+A*C=A*(B+C)$
#include <cstdio>
#include <algorithm>
#include <cstring>
#define lson (now << 1)
#define rson (now << 1 | 1)
#define ll long long
#define setIO(s) freopen(s".in", "r" , stdin)
using namespace std;
const int N = 200003;
const ll mod = 1000000007;
struct Matrix
{
int n, m;
ll a[4][4];
ll * operator[] (int x) { return a[x]; }
inline void re()
{
for(int i = 0; i < 3 ; ++i)
for(int j = 0; j < 3; ++j) a[i][j] = 0;
}
inline void I()
{
re();
for(int i = 0; i < 3 ; ++i) a[i][i] = 1ll;
}
Matrix friend operator * (Matrix a, Matrix b)
{
Matrix c;
c.re();
int i , j , k;
for(i = 0; i < a.n ; ++i)
{
for(j = 0; j < b.m ; ++j)
for(k = 0; k < a.m ; ++k)
{
c[i][j] = (c[i][j] + (a[i][k] * b[k][j]) % mod) % mod;
}
}
c.n = a.n , c.m = b.m;
return c;
}
Matrix friend operator + (Matrix a, Matrix b)
{
Matrix c;
c.n = 2, c.m = 1;
for(int i = 0; i < c.n ; ++i)
{
for(int j = 0; j < c.m; ++j) c[i][j] = (a[i][j] + b[i][j]) % mod;
}
return c;
}
}A[N], M, fib1, v;
Matrix operator ^ (Matrix a, int k)
{
Matrix tmp;
tmp.n = tmp.m = 2;
for(tmp.I(); k ; a = a * a, k >>= 1) if(k & 1) tmp = tmp * a;
return tmp;
}
inline void init()
{
M.re(), fib1.re();
M.n = M.m = 2;
M[0][0] = 0, M[0][1] = 1, M[1][0] = 1, M[1][1] = 1;
fib1.n = 2, fib1.m = 1;
fib1[0][0] = 0, fib1[1][0] = 1;
}
int n , m ;
struct Node
{
Matrix sum, lazy;
int tag;
}t[N << 2];
inline void pushup(int l, int r, int now)
{
int mid = (l + r) >> 1;
t[now].sum = t[now << 1].sum;
if(r > mid) t[now].sum = t[now].sum + t[now << 1 | 1].sum;
}
inline void mark(int now, Matrix f)
{
t[now].sum = f * t[now].sum ;
t[now].lazy = t[now].lazy * f;
t[now].tag = 1;
}
inline void pushdown(int l, int r, int now)
{
int mid = (l + r) >> 1;
if(t[now].tag)
{
mark(lson, t[now].lazy);
if(r > mid) mark(rson, t[now].lazy);
t[now].lazy.I(), t[now].tag = 0;
}
}
void build(int l, int r, int now)
{
t[now].lazy.n = t[now].lazy.m = 2;
t[now].lazy.I();
t[now].tag = 0;
if(l == r)
{
t[now].sum = A[l];
return ;
}
int mid = (l + r) >> 1;
if(mid >= l) build(l, mid, lson);
if(r > mid) build(mid + 1, r, rson);
pushup(l, r, now);
}
void update(int l, int r, int now, int L, int R)
{
if(l >= L && r <= R)
{
mark(now , v);
return ;
}
pushdown(l, r, now);
int mid = (l + r) >> 1;
if(L <= mid) update(l, mid, lson, L, R);
if(R > mid) update(mid + 1, r, rson, L, R);
pushup(l, r, now);
}
ll query(int l, int r, int now, int L, int R)
{
if(l >= L && r <= R) return t[now].sum[1][0];
pushdown(l, r, now);
int mid = (l + r) >> 1;
ll g = 0;
if(L <= mid) g += query(l, mid, lson, L, R);
if(R > mid) g += query(mid + 1, r, rson, L, R);
return (g % mod);
}
int main()
{
// setIO("input");
init();
int i , j, x;
scanf("%d%d", &n, &m);
for(i = 1; i <= n ; ++i)
{
scanf("%d", &x), A[i] = (M ^ (x - 1)) * fib1;
}
build(1, n, 1);
for(int cas = 1, op , l, r, x; cas <= m ; ++cas)
{
scanf("%d", &op);
if(op == 1)
{
scanf("%d%d%d", &l, &r, &x);
if(x == 0) continue;
v = M ^ x;
update(1, n, 1, l, r);
}
if(op == 2)
{
scanf("%d%d", &l, &r);
printf("%lld\n", query(1, n, 1, l, r));
}
}
return 0;
}