C. Sasha and Array

Codeforces

IDCF718C

Time5000ms

Memory256MB

Difficulty—

data structuresmathmatrices

English · Original

Chinese · Translation

Formal · Original

Sasha has an array of integers _a_1, _a_2, ..., _a__n_. You have to perform _m_ queries. There might be queries of two types: 1. _1 l r x_ — increase all integers on the segment from _l_ to _r_ by values _x_; 2. _2 l r_ — find , where _f_(_x_) is the _x_\-th Fibonacci number. As this number may be large, you only have to find it modulo 109 + 7. In this problem we define Fibonacci numbers as follows: _f_(1) = 1, _f_(2) = 1, _f_(_x_) = _f_(_x_ - 1) + _f_(_x_ - 2) for all _x_ > 2. Sasha is a very talented boy and he managed to perform all queries in five seconds. Will you be able to write the program that performs as well as Sasha? ## Input The first line of the input contains two integers _n_ and _m_ (1 ≤ _n_ ≤ 100 000, 1 ≤ _m_ ≤ 100 000) — the number of elements in the array and the number of queries respectively. The next line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109). Then follow _m_ lines with queries descriptions. Each of them contains integers _tp__i_, _l__i_, _r__i_ and may be _x__i_ (1 ≤ _tp__i_ ≤ 2, 1 ≤ _l__i_ ≤ _r__i_ ≤ _n_, 1 ≤ _x__i_ ≤ 109). Here _tp__i_ = 1 corresponds to the queries of the first type and _tp__i_ corresponds to the queries of the second type. It's guaranteed that the input will contains at least one query of the second type. ## Output For each query of the second type print the answer modulo 109 + 7. [samples] ## Note Initially, array _a_ is equal to 1, 1, 2, 1, 1. The answer for the first query of the second type is _f_(1) + _f_(1) + _f_(2) + _f_(1) + _f_(1) = 1 + 1 + 1 + 1 + 1 = 5. After the query _1 2 4 2_ array _a_ is equal to 1, 3, 4, 3, 1. The answer for the second query of the second type is _f_(3) + _f_(4) + _f_(3) = 2 + 3 + 2 = 7. The answer for the third query of the second type is _f_(1) + _f_(3) + _f_(4) + _f_(3) + _f_(1) = 1 + 2 + 3 + 2 + 1 = 9.

Sasha 有一个整数数组 #cf_span[a1, a2, ..., an]。你需要处理 #cf_span[m] 个查询。查询有两种类型：在本题中，斐波那契数定义如下：#cf_span[f(1) = 1]，#cf_span[f(2) = 1]，对于所有 #cf_span[x > 2]，有 #cf_span[f(x) = f(x - 1) + f(x - 2)]。 Sasha 是一个非常有天赋的男孩，他能在五秒内完成所有查询。你能否写出一个同样高效的程序？输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 100 000]，#cf_span[1 ≤ m ≤ 100 000]），分别表示数组的元素个数和查询的个数。接下来的一行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 10^9]）。接下来的 #cf_span[m] 行为查询描述。每行包含整数 #cf_span[tpi]、#cf_span[li]、#cf_span[ri]，可能还包含 #cf_span[xi]（#cf_span[1 ≤ tpi ≤ 2]，#cf_span[1 ≤ li ≤ ri ≤ n]，#cf_span[1 ≤ xi ≤ 10^9]）。其中 #cf_span[tpi = 1] 对应第一类查询，#cf_span[tpi = 2] 对应第二类查询。保证输入中至少包含一个第二类查询。对于每个第二类查询，请输出答案对 #cf_span[10^9 + 7] 取模的结果。初始时，数组 #cf_span[a] 为 #cf_span[1]、#cf_span[1]、#cf_span[2]、#cf_span[1]、#cf_span[1]。第一个第二类查询的答案为 #cf_span[f(1) + f(1) + f(2) + f(1) + f(1) = 1 + 1 + 1 + 1 + 1 = 5]。在执行查询 _1 2 4 2_ 后，数组 #cf_span[a] 变为 #cf_span[1]、#cf_span[3]、#cf_span[4]、#cf_span[3]、#cf_span[1]。第二个第二类查询的答案为 #cf_span[f(3) + f(4) + f(3) = 2 + 3 + 2 = 7]。第三个第二类查询的答案为 #cf_span[f(1) + f(3) + f(4) + f(3) + f(1) = 1 + 2 + 3 + 2 + 1 = 9]。 ## Input 输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 100 000]，#cf_span[1 ≤ m ≤ 100 000]），分别表示数组的元素个数和查询的个数。接下来的一行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 10^9]）。接下来的 #cf_span[m] 行为查询描述。每行包含整数 #cf_span[tpi]、#cf_span[li]、#cf_span[ri]，可能还包含 #cf_span[xi]（#cf_span[1 ≤ tpi ≤ 2]，#cf_span[1 ≤ li ≤ ri ≤ n]，#cf_span[1 ≤ xi ≤ 10^9]）。其中 #cf_span[tpi = 1] 对应第一类查询，#cf_span[tpi = 2] 对应第二类查询。保证输入中至少包含一个第二类查询。 ## Output 对于每个第二类查询，请输出答案对 #cf_span[10^9 + 7] 取模的结果。 [samples] ## Note 初始时，数组 #cf_span[a] 为 #cf_span[1]、#cf_span[1]、#cf_span[2]、#cf_span[1]、#cf_span[1]。第一个第二类查询的答案为 #cf_span[f(1) + f(1) + f(2) + f(1) + f(1) = 1 + 1 + 1 + 1 + 1 = 5]。在执行查询 _1 2 4 2_ 后，数组 #cf_span[a] 变为 #cf_span[1]、#cf_span[3]、#cf_span[4]、#cf_span[3]、#cf_span[1]。第二个第二类查询的答案为 #cf_span[f(3) + f(4) + f(3) = 2 + 3 + 2 = 7]。第三个第二类查询的答案为 #cf_span[f(1) + f(3) + f(4) + f(3) + f(1) = 1 + 2 + 3 + 2 + 1 = 9]。

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ denote the length of the array and number of queries, respectively. Let $ A = (a_1, a_2, \dots, a_n) $ be the initial array of integers. Define the Fibonacci sequence $ f: \mathbb{Z}^+ \to \mathbb{Z}^+ $ as: $$ f(1) = 1, \quad f(2) = 1, \quad f(x) = f(x-1) + f(x-2) \text{ for } x > 2. $$ **Constraints** 1. $ 1 \leq n \leq 100{,}000 $ 2. $ 1 \leq m \leq 100{,}000 $ 3. $ 1 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $ 4. For each query $ j \in \{1, \dots, m\} $: - $ \text{tp}_j \in \{1, 2\} $ - $ 1 \leq l_j \leq r_j \leq n $ - If $ \text{tp}_j = 1 $, then $ 1 \leq x_j \leq 10^9 $; if $ \text{tp}_j = 2 $, no $ x_j $ is provided. **Operations** For each query $ j $: - If $ \text{tp}_j = 1 $: update $ a_i \leftarrow a_i + x_j $ for all $ i \in \{l_j, l_j+1, \dots, r_j\} $. - If $ \text{tp}_j = 2 $: compute $ S_j = \sum_{i=l_j}^{r_j} f(a_i) \mod (10^9 + 7) $. **Objective** For each query of type $ \text{tp}_j = 2 $, output $ S_j $.

Samples

Input #1

Output #1

5
7
9

API Response (JSON)

{
  "problem": {
    "name": "C. Sasha and Array",
    "description": {
      "content": "Sasha has an array of integers _a_1, _a_2, ..., _a__n_. You have to perform _m_ queries. There might be queries of two types: 1.  _1 l r x_ — increase all integers on the segment from _l_ to _r_ by v",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF718C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Sasha has an array of integers _a_1, _a_2, ..., _a__n_. You have to perform _m_ queries. There might be queries of two types:\n\n1.  _1 l r x_ — increase all integers on the segment from _l_ to _r_ by v...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Sasha 有一个整数数组 #cf_span[a1, a2, ..., an]。你需要处理 #cf_span[m] 个查询。查询有两种类型：\n\n在本题中，斐波那契数定义如下：#cf_span[f(1) = 1]，#cf_span[f(2) = 1]，对于所有 #cf_span[x > 2]，有 #cf_span[f(x) = f(x - 1) + f(x - 2)]。\n\nSasha 是一个非常有天...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the length of the array and number of queries, respectively.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the initial array of integers.  \nDefine the ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments