CF316E3 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}$，你需要计算如下和：，其中 $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\leq 100$，$m\leq 10000$，且不会有第 $3$ 种类型的操作。 对于获得 $70$ 分的输入限制（子任务 E1+E2）： - 保证只会有第 $1$ 种和第 $2$ 种类型的操作。 对于获得 $100$ 分的输入限制（子任务 E1+E2+E3）： - 没有额外限制。

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

由 ChatGPT 4.1 翻译