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.

题意概述

给定一个长度为$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 数列的任意一项。其前缀和亦然。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#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;
}
OI > Data Structure
#Segment Tree
DZY Loves Fibonacci Numbers
https://regmsif.cf/2017/07/20/oi/dzy-loves-fibonacci-numbers/
作者
RegMs If
发布于
2017年7月20日
许可协议