Codeforces 446C
题意：给出一个数列，每次可以选取一个区间，按顺序加上第$i$个斐波那契数进行更新，也可以查询某一个区间的总和。
性质一
$\sum_{i=1}^n f_i = f_{n+2} - f_2$
证明即累加$f_1=f_3-f_2$
性质二
两个斐波那契数列相加仍然是斐波那契数列，只是前两项不一样，并且可以通过$f$求出这个数列，即$g_i=a \times f_{n-2} + b \times f_{n-1}$
计算方法通过累加很容易发现。
那么这里就可以线段树维护了，线段树维护每个区间的前两项和区间和，因为性质二所以区间信息可以方便pushdown
顺便提一下pushup：显然区间和信息可合并pushdown：性质二query：性质二update：性质二
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 300000 + 5;
const LL MO = 1e9 + 9;
#define lc (o << 1)
#define rc (o << 1 | 1)
#define M ((l + r) >> 1)
#define ls lc, l, M
#define rs rc, M + 1, r
int n, Q, a[MAXN];
LL f[MAXN * 4], sumv[MAXN * 4], f1[MAXN * 4], f2[MAXN * 4];
LL g(LL a, LL b, LL n) {
if (n == 1) return a;
if (n == 2) return b;
return (f[n - 2] * a % MO + f[n - 1] * b % MO) % MO;
}
LL sum(LL a, LL b, LL n) {
if (n == 1) return a;
if (n == 2) return a + b;
return ((g(a, b, n + 2) - b) % MO + MO) % MO;
}
void pushup(int o) {(sumv[o] = sumv[lc] + sumv[rc]) %= MO;}
void pushdown(int o, int l, int r) {
if (f1[o]) {
int len = r - l + 1;
(f1[lc] += f1[o]) %= MO;
(f2[lc] += f2[o]) %= MO;
(sumv[lc] += sum(f1[o], f2[o], len - len / 2)) %= MO;
(f1[rc] += g(f1[o], f2[o], len - len / 2 + 1)) %= MO;
(f2[rc] += g(f1[o], f2[o], len - len / 2 + 2)) %= MO;
(sumv[rc] += sum(g(f1[o], f2[o], len - len / 2 + 1), g(f1[o], f2[o], len - len / 2 + 2), len / 2)) %= MO;
f1[o] = f2[o] = 0;
}
}
void build(int o, int l, int r) {
if (l == r) return sumv[o] = a[l], void();
build(ls), build(rs);
pushup(o);
}
void update(int o, int l, int r, int x, int y) {
if (l != r) pushdown(o, l, r);
if (x <= l && r <= y) {
(f1[o] += f[l - x + 1]) %= MO, (f2[o] += f[l - x + 2]) %= MO;
(sumv[o] += sum(f[l - x + 1], f[l - x + 2], r - l + 1)) %= MO;
return ;
}
if (x <= M) update(ls, x, y);
if (M < y) update(rs, x, y);
pushup(o);
}
LL query(int o, int l, int r, int x, int y) {
if (l != r) pushdown(o, l, r);
if (x <= l && r <= y) return sumv[o];
LL ret = 0;
if (x <= M) (ret += query(ls, x, y)) %= MO;
if (M < y) (ret += query(rs, x, y)) %= MO;
return ret;
}
void clean() {
}
int solve() {
cin >> n >> Q;
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
f[1] = f[2] = 1;
for (int i = 3; i <= n + 2; ++i) (f[i] += f[i - 1] + f[i - 2]) %= MO;
build(1, 1, n);
while (Q--) {
int ty, l, r; scanf("%d%d%d", &ty, &l, &r);
if (ty == 1) {
update(1, 1, n, l, r);
} else {
printf("%lld\n", query(1, 1, n, l, r));
}
}
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
/*
10 100
0 0 0 0 0 0 0 0 0 0
1 1 10
2 9 9
5 100
0 0 0 0 0
1 1 5
2 5 5
4 400
1 2 3 4
1 1 4
2 1 4
1 2 4
2 1 3
*/
