CF316E2 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}$，将区间 $[l_{i}, 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 \leq 100$，$m \leq 10000$，且不会有第 $3$ 种类型的操作。 对于获得 $70$ 分的输入限制（子任务 E1+E2）： - 保证只会有第 $1$ 和第 $2$ 种类型的操作。 对于获得 $100$ 分的输入限制（子任务 E1+E2+E3）： - 无额外限制。

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

由 ChatGPT 4.1 翻译