题目描述
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.
题意概述
给定一个长度为$n$的数列,第$i$个数为$a_i$。有两种操作:①对于$i \in [l, r]$,将$a_i$加上$F_{i-l+1}$;②询问区间$[l, r]$内的数字之和。其中$F_i$表示Fibonacci数列的第$i$项。操作有$m$次。
数据范围:$1 \le n, m \le 3 \times 10^5, \; 1 \le a_i \le 10^9$。
算法分析
在一个Fibonacci数列上加一个Fibonacci数列,其结果仍然是Fibonacci数列。而对于一个Fibonacci数列,只要知道前两个数,就能知道接下来的所有数。可以用线段树来维护,对于每一个节点记录下区间和,以及可以代表这个区间上Fibonacci数列的前两个数。设前两个数分别为$a, b$,预处理出Fibonacci数列每一项$a$和$b$的系数,即可在$O(1)$时间内计算出Fibonacci数列的任意一项。其前缀和亦然。
代码
#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; }