题目链接：http://codeforces.com/contest/719/problem/E
题意：操作1将[l, r] + x;
操作2求f[l] + ... + f[r];
题解：注意矩阵可以是a*(b + c) = a*b + a*c ，还有update的时候传入矩阵
//#pragma comment(linker, "/STACK:102400000, 102400000")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair <int, int> P;
const int N = 1e5 + ;
LL a[N], mod = 1e9 + ;
struct data {
LL mat[][];
data() {
mat[][] = mat[][] = mat[][] = ;
mat[][] = ;
}
void init() {
mat[][] = mat[][] = ;
mat[][] = mat[][] = ;
}
}op;
struct SegTree {
int l, r;
data lazy;
data val;
}T[N << ]; data operator +(const data &a, const data &b) {
data ans;
for(int i = ; i <= ; ++i) {
for(int j = ; j <= ; ++j) {
ans.mat[i][j] = (a.mat[i][j] + b.mat[i][j]) % mod;
}
}
return ans;
} data operator *(const data &a, const data &b) {
data ans;
for(int i = ; i <= ; ++i) {
for(int j = ; j <= ; ++j) {
ans.mat[i][j] = ;
for(int k = ; k <= ; ++k) {
ans.mat[i][j] = (ans.mat[i][j] + a.mat[i][k] * b.mat[k][j] % mod) % mod;
}
}
}
return ans;
} data operator ^(data a, LL n) {
data ans;
for(int i = ; i <= ; ++i) {
for(int j = ; j <= ; ++j) {
ans.mat[i][j] = (i == j);
}
}
while(n) {
if(n & )
ans = ans * a;
a = a * a;
n >>= ;
}
return ans;
} bool cmp(const data &a) {
for(int i = ; i <= ; ++i) {
for(int j = ; j <= ; ++j) {
if(a.mat[i][j] != op.mat[i][j])
return false;
}
}
return true;
} inline void pushdown(int p) {
if(!cmp(T[p].lazy)) {
T[p << ].lazy = T[p].lazy * T[p << ].lazy;
T[(p << )|].lazy = T[p].lazy * T[(p << )|].lazy;
T[p << ].val = T[p << ].val * T[p].lazy;
T[(p << )|].val = T[(p << )|].val * T[p].lazy;
T[p].lazy.init();
}
} void build(int p, int l, int r) {
int mid = (l + r) >> ;
T[p].l = l, T[p].r = r, T[p].lazy.init();
if(l == r) {
scanf("%lld", a + l);
T[p].val = T[p].val ^ (a[l] - );
return ;
}
build(p << , l, mid);
build((p << )|, mid + , r);
T[p].val = T[p << ].val + T[(p << )|].val;
} void update(int p, int l, int r, data add) {
int mid = (T[p].l + T[p].r) >> ;
if(T[p].l == l && T[p].r == r) {
T[p].lazy = add * T[p].lazy;
T[p].val = T[p].val * add;
return ;
}
pushdown(p);
if(r <= mid) {
update(p << , l, r, add);
} else if(l > mid) {
update((p << )|, l, r, add);
} else {
update(p << , l, mid, add);
update((p << )|, mid + , r, add);
}
T[p].val = T[p << ].val + T[(p << )|].val;
} LL query(int p, int l, int r) {
int mid = (T[p].l + T[p].r) >> ;
if(T[p].l == l && T[p].r == r) {
return T[p].val.mat[][];
}
pushdown(p);
if(r <= mid) {
return query(p << , l, r);
} else if(l > mid) {
return query((p << )|, l, r);
} else {
return (query(p << , l, mid) + query((p << )|, mid + , r)) % mod;
}
} int main()
{
op.init();
int n, m;
scanf("%d %d", &n, &m);
build(, , n);
int c, l, r;
LL add;
while(m--) {
scanf("%d %d %d", &c, &l, &r);
if(c == ) {
scanf("%lld", &add);
data temp;
update(, l, r, temp ^ add);
} else {
printf("%lld\n", query(, l, r));
}
}
return ;
}