# DZY Loves Fibonacci Numbers

## 题目描述

In mathematical terms, the sequence $F_n$ of Fibonacci numbers is defined by the recurrence relation:
$$F_1=1, \; F_2=1, \; F_n=F_{n-1}+F_{n-2} \; (n \gt 2)$$
DZY loves Fibonacci numbers very much. Today DZY gives you an array consisting of $n$ integers: $a_1, a_2, \ldots, a_n$. Moreover, there are $m$ queries, each query has one of the two types:

• Format of the query “1 $l$ $r$”. In reply to the query, you need to add $F_{i-l+1}$ to each element $a_i$, where $l \le i \le r$.
• Format of the query “2 $l$ $r$”. In reply to the query you should output the value of $\sum_{i=l}^r a_i$ modulo $1000000009$ ($10^9+9$).

Help DZY reply to all the queries.

## 代码

#include <cstdio>
#include <iostream>
using namespace std;
const long long mod = 1000000009ll;
struct node_type {
long long l, r, val[2], sum, child[2];
} node[1000001];
long long n, m, o, l, r, tot = 1, a[300001], x[300001][2], y[300001][2];
void build_tree(int root) {
if (node[root].l == node[root].r) return; long long mid = node[root].l + node[root].r >> 1;
node[++tot].l = node[root].l, node[tot].r = mid, node[root].child[0] = tot, build_tree(tot);
node[++tot].l = mid + 1, node[tot].r = node[root].r, node[root].child[1] = tot, build_tree(tot);
}
void push_down(int root) {
if (node[root].l == node[root].r || node[root].val[0] == 0 && node[root].val[1] == 0) return;
if (node[node[root].child[0]].l == node[node[root].child[0]].r) node[node[root].child[0]].sum += node[root].val[0];
else {
(node[node[root].child[0]].val[0] += node[root].val[0]) %= mod, (node[node[root].child[0]].val[1] += node[root].val[1]) %= mod;
node[node[root].child[0]].sum += y[node[node[root].child[0]].r - node[node[root].child[0]].l + 1][0] * node[root].val[0] % mod;
node[node[root].child[0]].sum += y[node[node[root].child[0]].r - node[node[root].child[0]].l + 1][1] * node[root].val[1] % mod;
}
long long p = (x[node[node[root].child[0]].r - node[node[root].child[0]].l + 2][0] * node[root].val[0] + x[node[node[root].child[0]].r - node[node[root].child[0]].l + 2][1] * node[root].val[1]) % mod;
long long q = (x[node[node[root].child[0]].r - node[node[root].child[0]].l + 3][0] * node[root].val[0] + x[node[node[root].child[0]].r - node[node[root].child[0]].l + 3][1] * node[root].val[1]) % mod;
if (node[node[root].child[1]].l == node[node[root].child[1]].r) node[node[root].child[1]].sum += p;
else {
(node[node[root].child[1]].val[0] += p) %= mod, (node[node[root].child[1]].val[1] += q) %= mod;
node[node[root].child[1]].sum += y[node[node[root].child[1]].r - node[node[root].child[1]].l + 1][0] * p % mod;
node[node[root].child[1]].sum += y[node[node[root].child[1]].r - node[node[root].child[1]].l + 1][1] * q % mod;
}
node[root].val[0] = node[root].val[1] = 0;
}
void push_up(int root) {
if (node[root].l == node[root].r) return;
node[root].sum = node[node[root].child[0]].sum + node[node[root].child[1]].sum;
}
void insert_line(int root, int l, int r, int val) {
if (node[root].r < l || node[root].l > r) return;
if (node[root].l >= l && node[root].r <= r) {
if (node[root].l == node[root].r) node[root].sum += x[val][0] + x[val][1];
else {
(node[root].val[0] += x[val][0] + x[val][1]) %= mod;
(node[root].val[1] += x[val + 1][0] + x[val + 1][1]) %= mod;
node[root].sum += y[node[root].r - node[root].l + 1][0] * (x[val][0] + x[val][1]) % mod;
node[root].sum += y[node[root].r - node[root].l + 1][1] * (x[val + 1][0] + x[val + 1][1]) % mod;
}
return;
}
push_down(root);
insert_line(node[root].child[0], l, r, val);
insert_line(node[root].child[1], l, r, max(1ll, val + node[node[root].child[1]].l - max((long long) l, node[node[root].child[0]].l)));
push_up(root);
}
long long get_sum(int root, int l, int r) {
if (node[root].r < l || node[root].l > r) return 0;
if (node[root].l >= l && node[root].r <= r) return node[root].sum;
long long ret;
push_down(root);
ret = get_sum(node[root].child[0], l, r) + get_sum(node[root].child[1], l, r);
push_up(root);
return ret;
}
int main()
{
scanf("%lld%lld", &n, &m);
x[1][0] = x[2][1] = y[1][0] = y[2][0] = y[2][1] = 1;
for (int i = 3; i <= n; ++i) {
x[i][0] = (x[i - 1][0] + x[i - 2][0]) % mod;
x[i][1] = (x[i - 1][1] + x[i - 2][1]) % mod;
y[i][0] = (y[i - 1][0] + x[i][0]) % mod;
y[i][1] = (y[i - 1][1] + x[i][1]) % mod;
}
node[1].l = 1, node[1].r = n, build_tree(1);
for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]), a[i] += a[i - 1];
while (m--) {
scanf("%lld%lld%lld", &o, &l, &r);
if (o == 1) insert_line(1, l, r, 1);
else printf("%lld\n", ((get_sum(1, l, r) + a[r] - a[l - 1]) % mod + mod) % mod);
}
return 0;
}


418 I'm a teapot