CF316E1 Summer Homework

三岁时，Smart Beaver 就掌握了所有的算术运算，老师惊讶地给了他这个暑假作业： 给定一个整数序列 $a_{1},a_{2},...,a_{n}$。你需要对其进行 $m$ 次连续操作，操作类型如下： 1. 给定数字 $x_{i}$ 和 $v_{i}$，将 $a_{x_{i}}$ 的值赋为 $v_{i}$。 2. 给定数字 $l_{i}$ 和 $r_{i}$，你需要计算 $\sum_{j=l_{i}}^{r_{i}} a_{j} f_{j-l_{i}}$，其中 $f_{0}=f_{1}=1$，对于 $i \geq 2$，有 $f_{i}=f_{i-1}+f_{i-2}$。 3. 给定三个数字 $l_{i}$、$r_{i}$、$d_{i}$，你需要将所有 $x$ 满足 $l_{i} \leq x \leq r_{i}$ 的 $a_{x}$ 增加 $d_{i}$。 Smart Beaver 计划去加拿大大湖区旅行，所以他请你帮他解决这个问题。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 2 \cdot 10^{5}$），分别表示序列中整数的个数和操作的次数。第二行包含 $n$ 个整数 $a_{1},a_{2},...,a_{n}$（$0 \leq a_{i} \leq 10^{5}$）。接下来有 $m$ 行，每行描述一个操作。每行以一个整数 $t_{i}$（$1 \leq t_{i} \leq 3$）开头，表示操作类型： - 如果 $t_{i}=1$，接下来有两个整数 $x_{i}$、$v_{i}$（$1 \leq x_{i} \leq n, 0 \leq v_{i} \leq 10^{5}$）； - 如果 $t_{i}=2$，接下来有两个整数 $l_{i}$、$r_{i}$（$1 \leq l_{i} \leq r_{i} \leq n$）； - 如果 $t_{i}=3$，接下来有三个整数 $l_{i}$、$r_{i}$、$d_{i}$（$1 \leq l_{i} \leq r_{i} \leq n, 0 \leq d_{i} \leq 10^{5}$）。 对于获得 $30$ 分的输入限制（子任务 E1）： - 保证 $n$ 不超过 $100$，$m$ 不超过 $10000$，且不会有第 $3$ 种类型的操作。 对于获得 $70$ 分的输入限制（子任务 E1+E2）： - 保证只会有第 $1$ 种和第 $2$ 种类型的操作。 对于获得 $100$ 分的输入限制（子任务 E1+E2+E3）： - 无额外限制。

对于每个查询操作，输出计算得到的和对 $1000000000$（$10^{9}$）取模后的结果。

由 ChatGPT 4.1 翻译