P16389 [IATI 2024] Five

由于不可预见的情况，本题并非第五题。 一家名为“Ko & co”的民调机构最近的一项调查发现，没有人喜欢数字 $1$ 到 $4$。因此我们将关注下一个数字 $5$，并希望它不会重蹈其前辈的悲惨命运。 考虑如下定义在正负整数下标上的序列： - $x_0 = 0$ - $x_1 = 1$ - $x_2 = 2$ - $x_3 = 3$ - $x_4 = 4$ - 对于任意整数 $k$，有 $x_{k+5} = 5 \times x_{k+4} + 4 \times x_{k+3} + 3 \times x_{k+2} + 2 \times x_{k+1} + 1 \times x_{k}$。 注意，该等式唯一确定了所有正负下标的值（例如 $x_5 = 40$，$x_6 = 230$，$\dots$ 以及 $x_{-1} = -22$，$x_{-2} = 33$，$\dots$）。 给定一个包含 $n$ 个数的数组 $a_1, a_2, \dots, a_n$。请编写一个程序 $\texttt{five}$，支持以下 $2$ 种操作： - **查询**：给定参数 $l, r$，求 $x_{a_{l}} + x_{a_{l + 1}} + ... + x_{a_{r}} = \sum_{i = l}^{r} x_{a_{i}}$。由于答案可能非常大，请输出其对 $M = 10 ^ 8 + 543$ 取模的结果。 - **更新**：给定参数 $l, r, value$，则对于每个 $l \leq i \leq r$，$a_i$ 的新值变为 $a_i + value$。

第一行包含两个整数 $n$ 和 $q$。 接下来一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$。接下来的 $q$ 行，每行包含三个整数 $type, l, r$。 若 $type = 1$，则该行为一个**查询**。 若 $type = 2$，则该行为一个**更新**，并额外包含一个整数 $value$。

对于每个**查询**，在新的一行输出该查询的答案。

### 样例解释 初始时 $a_1 = 1$，$x_{a_{1}} = 1$。第一次**更新**后 $a_1 = -1$，$x_{a_{1}} = -22$。第二次**更新**后 $a_1 = 7$，$x_{a_{1}} = 1330$。 ### 数据范围 - $1 \leq n \leq 100\,000$ - $1 \leq q \leq 200\,000$ - $1 \leq l \leq r \leq n$ - $-M < a_i, value < M$ ### 子任务 | **子任务** | **分数** | **附加约束** | | :---: | :---: | :---: | | $1$ | $5$ | $0 \leq a_i \leq 10^6$ 且仅有**查询**操作 | | $2$ | $19$ | $0 \leq a_i, value$ 且 $l = r$ | | $3$ | $19$ | $0 \leq a_i, value$ 且 $q \leq 20\,000$ | | $4$ | $19$ | $q \leq 20\,000$ | | $5$ | $19$ | $q \leq 100\,000$ | | $6$ | $19$ | 无 | 只有当某个子任务的所有测试数据及其所依赖子任务的全部测试数据均成功通过时，该子任务的分数才会被给出。 翻译由 DeepSeek V4 Pro 完成