Description
你需要维护一个长度为(n leq 300000) 的数列，兹词两个操作：
1.给一个区间加上一个fibonacci数列，规定(f[0] = 0, f[1] = 1, f[2] = 1)
2.查询一段区间的和。对1e9+9取模
操作个数m不超过300000.
Solution
这一题其实要考虑Fibonacci数列的两个性质:
(i)(sum_{i = 1}^{n} fib(i) = f(n + 2) - 1)
(ii)令(S_i = S_{i - 1} + S_{i - 2}), 其中(S_1 = a, S_2 = b)
那么(S_i = aFib(i - 1) + bFib(i - 2))
那么就很好做了， 在线段树中， 我们要只要记数列的前两项就可以方便的对数列进行求和，pushdown等操作.
这题细节比较多，相关部分见代码。
Code
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define drep(i, a, b) for(int i = (a), i##_end_ = (b); i >= i##_end_; --i)
#define clar(a, b) memset((a), (b), sizeof(a))
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug(s) debug("The massage in line %d, Function %s: %s
", __LINE__, __FUNCTION__, s)
typedef long long LL;
typedef long double LD;
const int BUF_SIZE = (int)1e6 + 10;
struct fastIO {
char buf[BUF_SIZE], buf1[BUF_SIZE];
int cur, cur1;
FILE *in, *out;
fastIO() {
cur = BUF_SIZE, in = stdin, out = stdout;
cur1 = 0;
}
inline char getchar() {
if(cur == BUF_SIZE) fread(buf, BUF_SIZE, 1, in), cur = 0;
return *(buf + (cur++));
}
inline void putchar(char ch) {
*(buf1 + (cur1++)) = ch;
if (cur1 == BUF_SIZE) fwrite(buf1, BUF_SIZE, 1, out), cur1 = 0;
}
inline int flush() {
if (cur1 > 0) fwrite(buf1, cur1, 1, out);
return cur1 = 0;
}
}IO;
#define getchar IO.getchar
#define putchar IO.putchar
int read() {
char ch = getchar();
int x = 0, flag = 1;
for(;!isdigit(ch); ch = getchar()) if(ch == '-') flag *= -1;
for(;isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
return x * flag;
}
void write(int x) {
if(x < 0) putchar('-'), x = -x;
if(x >= 10) write(x / 10);
putchar(x % 10 + 48);
}
void putString(char s[], char EndChar = '
') {
rep(i, 0, strlen(s) - 1) putchar(*(s + i));
if(~EndChar) putchar(EndChar);
}
#define Maxn 300009
const LL Mod = 1000000009;
int n, a[Maxn], m; LL f[Maxn];
struct node { LL x, y; };
LL FibDelta(LL F1, LL F2, LL len) {
LL res = 0;
if(len >= 1) (res += F1) %= Mod;
if(len >= 2) (res += F2) %= Mod;
if(len >= 3) (res += (F2 * (f[len + 1] - 2ll) % Mod + F1 * (f[len] - 1ll) % Mod) % Mod) %= Mod;
return res;
}// It needs to analysis in different conditions
node FibForward(node s, int len) {
LL c = s.x * f[len] % Mod + s.y * f[len + 1] % Mod, d = s.x * f[len + 1] % Mod + s.y * f[len + 2] % Mod;
return (node){c % Mod, d % Mod};
}
namespace SGMT_tree {
LL tree[Maxn << 2], beg[Maxn << 2][2], val[Maxn << 2];
#define lc(x) (x) << 1
#define rc(x) (x) << 1 | 1
#define ls rt << 1, l, mid
#define rs rt << 1 | 1, mid + 1, r
void pushup(int rt) { tree[rt] = (1ll * tree[lc(rt)] + 1ll * tree[rc(rt)]) % Mod; }
void pushdown(int rt, int l, int r) {
int mid = (l + r) >> 1;
if(val[rt]) {
LL &a = beg[rt][0], &b = beg[rt][1];
(beg[lc(rt)][0] += a) %= Mod, (beg[lc(rt)][1] += b) %= Mod;
(tree[lc(rt)] += FibDelta(a, b, mid - l + 1)) %= Mod;
val[lc(rt)] = 1;
LL c = a * f[mid - l] + b * f[mid - l + 1], d = a * f[mid - l + 1] + b * f[mid - l + 2];
c %= Mod, d %= Mod;
(beg[rc(rt)][0] += c) %= Mod, (beg[rc(rt)][1] += d) %= Mod;
(tree[rc(rt)] += FibDelta(c, d, r - mid)) %= Mod;
val[rc(rt)] = 1;
beg[rt][0] = beg[rt][1] = 0;
val[rt] = 0;
}
}
void build(int rt, int l, int r) {
if(l == r) {
tree[rt] = a[l];
return ;
}
int mid = (l + r) >> 1;
build(ls), build(rs);
pushup(rt);
}
void modify(int rt, int l, int r, int x, int y, int p1, int p2) {
if(x <= l && r <= y) {
(beg[rt][0] += p1) %= Mod, (beg[rt][1] += p2) %= Mod;
(tree[rt] += FibDelta(p1, p2, r - l + 1)) %= Mod;
val[rt] = 1;
return ;
}
int mid = (l + r) >> 1;
pushdown(rt, l, r);
if(y <= mid) modify(ls, x, y, p1, p2);
else if(mid + 1 <= x) modify(rs, x, y, p1, p2);
else {
modify(ls, x, mid, p1, p2); /**/
node z = FibForward((node){p1, p2}, mid - x);/**/
//F[i] -> F[i + mid - x]: p1 -> z.x, p2 -> z.y
modify(rs, mid + 1, y, z.x, z.y);/*The InterVal needs to move*/
}
pushup(rt);
}
int query(int rt, int l, int r, int x, int y) {
if(x <= l && r <= y) return tree[rt];
int mid = (l + r) >> 1; pushdown(rt, l, r);
if(y <= mid) return query(ls, x, y);
else if(mid + 1 <= x) return query(rs, x, y);
else return (1ll * query(ls, x, y) + 1ll * query(rs, x, y)) % Mod;
}
#undef lc
#undef rc
#undef ls
#undef rs
}
namespace INIT {
void Main() {
n = read(), m = read();
f[1] = 1; f[2] = 1;
rep(i, 3, n + 4) f[i] = (f[i - 1] * 1ll + f[i - 2]) % Mod;
rep(i, 1, n) a[i] = read();
SGMT_tree :: build(1, 1, n);
}
}
namespace SOLVE {
void Main() {
rep(i, 1, m) {
int opt = read();
if(opt == 1) {
int x = read(), y = read();
SGMT_tree :: modify(1, 1, n, x, y, 1, 1);
}
if(opt == 2) {
int x = read(), y = read();
write(SGMT_tree :: query(1, 1, n, x, y)), putchar('
');
}
}
}
}
int main() {
freopen("CF446C.in", "r", stdin);
freopen("CF446C.out", "w", stdout);
INIT :: Main();
SOLVE :: Main();
#ifdef Qrsikno
debug("
Running time: %.3lf(s)
", clock() * 1.0 / CLOCKS_PER_SEC);
#endif
return IO.flush();
}