http://codeforces.com/contest/447/problem/E
题意： 给定一个数组， m次操作，
1 l r 表示区间修改， 每次 a[i] + Fibonacci[i-l+]
2 l r 区间求和
每次修改操作，只需要记录 每个点前两个值就可以了， 后面的和以及孩子需要加的值都可以通过这两个求出来。 推推公式就出来了。
注意 溢出。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 3e5+;
const int MOD = 1e9+;
LL sum[MAXN << ], addv1[MAXN << ], addv2[MAXN << ];
LL fib[MAXN], hhh[MAXN], fff[MAXN];
void pre_solve() {
fff[] = ;
fff[] = ;
fib[] = fib[] = ;
hhh[] = ;
for (int i = ; i < MAXN; i++) {
fib[i] = (fib[i-] + fib[i-]) % MOD;
fff[i] = (fff[i-] + fff[i-]) % MOD;
}
for (int i = ; i < MAXN; i++) {
hhh[i] = (fib[i-] + hhh[i-]) % MOD;
}
}
void push_up(int pos) {
sum[pos] = (sum[pos<<] + sum[pos<<|]) % MOD;
}
void update_add(int l, int r, int pos, LL val1, LL val2) {
addv1[pos] = (addv1[pos] + val1) % MOD;
addv2[pos] = (addv2[pos] + val2) % MOD;
int idx = (r - l + );
sum[pos] = (sum[pos] + fib[idx] * val1 % MOD + hhh[idx] * val2 % MOD) % MOD;
}
void push_down(int l, int r, int pos) {
int mid = (l + r) >> ;
update_add(l, mid, pos<<, addv1[pos], addv2[pos]);
update_add(mid+, r, pos<<|, (fff[mid+-l+]*addv1[pos]+fib[mid+-l]*addv2[pos])%MOD,
(fff[mid+-l+]*addv1[pos]+fib[mid+-l+]*addv2[pos])%MOD);
addv1[pos] = addv2[pos] = ;
}
void build (int l, int r, int pos) {
addv1[pos] = addv2[pos] = ;
if (l == r) {
scanf ("%I64d", sum+pos);
return ;
}
int mid = (l + r) >> ;
build(l, mid, pos<<);
build(mid+, r, pos<<|);
push_up(pos);
}
void update (int l, int r, int pos, int ua, int ub, LL x1, LL x2) {
if (ua <= l && ub >= r) {
update_add(l, r, pos, x1, x2);
return ;
}
push_down(l, r, pos);
int mid = (l + r) >> ;
if (ua <= mid) {
update(l, mid, pos<<, ua, ub, x1, x2);
}
if (ub > mid) {
if (ua <= mid) {
int tmp = max(l, ua);
LL t1 = (fff[mid+-tmp+]*x1+fib[mid+-tmp]*x2) % MOD;
LL t2 = (fff[mid+-tmp+]*x1+fib[mid+-tmp+]*x2) % MOD;
update(mid+, r, pos<<|, ua, ub, t1, t2);
} else {
update(mid+, r, pos<<|, ua, ub, x1, x2);
}
}
push_up(pos);
}
LL query (int l, int r, int pos, int ua, int ub) {
if (ua <= l && ub >= r) {
return sum[pos];
}
push_down(l, r, pos);
int mid = (l + r) >> ;
LL tmp = ;
if (ua <= mid)
{
tmp = (tmp + query(l, mid, pos<<, ua, ub)) % MOD;
}
if (ub > mid)
{
tmp = (tmp + query(mid+, r, pos<<|, ua, ub)) % MOD;
} return tmp;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int n, m;
pre_solve();
while (~ scanf ("%d%d", &n, &m)) {
build(, n, );
for (int i = ; i < m; i++) {
int op, u, v;
scanf ("%d%d%d", &op, &u, &v);
if (op == ) {
update(, n, , u, v, fib[], fib[]);
} else {
LL ans = query(, n, , u, v);
printf("%I64d\n", ans);
}
}
}
return ;
}