U128383 「hyOI2020」henry_y 的数列

给出一个长度为 $n$ 的正整数序列 $\{A_n\}$，维护 $q$ 个操作，操作有两种： * `1 l r a b c`：$\forall l \leq i \leq r, i \in \mathbb{N}$，令 $A_i$ 变为 $A_i + ai^2 + bi + c$； * `2 l r`：输出 $\min_{l \leq i \leq r} \{A_i\}$ 的值。

第一行，两个整数 $n, q$，分别表示序列长度和操作个数。 第二行，$n$ 个整数 $A_1, A_2, \ldots, A_n$，表示序列。 接下来 $q$ 行，每行三到五个整数，描述操作。

多行，每行一个整数，表示答案。

#### 样例解释 | 操作参数 | 意义 | $A_1$ | $A_2$ | $A_3$ | $A_4$ | $A_5$ | 输出 | | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | | 初始 | | 2 | 2 | 5 | 3 | 5 | | | `1 1 5 0 3 0` | 将 $[1, 5]$ 内的 $A_i$ 变为 $A_i + 3i$ | 5 | 8 | 14 | 15 | 20 | | | `1 2 3 1 0 1` | 将 $[2, 3]$ 内的 $A_i$ 变为 $A_i + i^2 + 1$ | 5 | 13 | 24 | 15 | 20 | | | `2 2 4` | 查询 $[2, 4]$ 内的 $A_i$ 的最小值 | 5 | 13 | 24 | 15 | 20 | 13 | | `1 1 5 0 2 3` | 将 $[1, 5]$ 内的 $A_i$ 变为 $A_i + 2i + 3$ | 10 | 20 | 33 | 26 | 33 | | | `1 1 5 2 1 1` | 将 $[1, 5]$ 内的 $A_i$ 变为 $A_i + 2i^2 + i + 1$ | 14 | 31 | 55 | 63 | 89 | | | `2 3 4` | 查询 $[3, 4]$ 内的 $A_i$ 的最小值 | 14 | 31 | 55 | 63 | 89 | 55 | #### 数据范围与提示 对于 $100\%$ 的数据，$1 \leq n, q \leq 10^5$，$0 \leq A_i, c \leq 10^{13}$，$0 \leq b \leq 10^8$，$0 \leq a \leq 10^3$，$1 \leq l \leq r \leq n$。 本题采用子任务评测。对于同个子任务，你只有通过该子任务内的所有测试点，才能拿到该子任务的分数。 | 子任务编号 | 约定 | 分值 | | :----------: | :----------------------------------: | :---------: | | $1$ | $n, q \leq 8000$ | $10$ | | $2$ | 数据有一定程度的随机 | $70$ | | $3$ | 询问次数不超过 $700$ 次 | $10$ | | $4$ | 无特殊限制 | $10$ | 关于「数据有一定程度的随机」的解释：该子任务内所有数据由以下方式生成。 * 首先**手动**决定 $n, q, X, Y, Z$ 的值，其中 $1 \leq n, q \leq 10^5$，$0 \leq X \leq 10^3$，$0 \leq Y \leq 10^8$，$0 \leq Z \leq 10^{13}$。 * 任意 $a$ 均在 $[0, X]$ 范围内等概率随机生成，$b$ 在 $[0, Y]$ 范围内等概率随机生成，$A_i, c$ 在 $[0, Z]$ 范围内等概率随机生成。 * 对于操作中的区间参数 $l, r$，生成方式为： - 首先等概率随机生成整数 $k \in [1, n]$，表示区间长度； - 再等概率随机生成整数 $l \in [1, n - k + 1]$，表示区间的左端点； - 计算 $r = l + k - 1$，表示区间的右端点。 #### 后记 很遗憾地告知大家，henry_y 走了。 他现在已经不在机房了。 这也就是为什么这道题的题目背景中没有 henry_y 的出现，也没有 Tsukimaru 的出现。 谨以此题，悼念我们永恒的 henry_y 男神老师。 这个人也许永远不回来了，也许明天回来！ ---- > **henry_y 18:43:40** >   \[图片\] > **henry_y 18:43:55** >   @Tsukimaru > **henry_y 18:44:10** >   ¿ > **henry_y 18:44:37** >   我就去吃了个晚饭回来怎么这个样子 > *Tsukimaru 撤回了一条消息* > **Tsukimaru 18:45:12** >   哦，是吗？ > **Tsukimaru 18:45:21** >   呵呵，那只是你的以为。 > **Tsukimaru 18:45:28** >   好的好的，我知道了。 > **Tsukimaru 18:45:33** >   不会是真的吧？ > *Tsukimaru 被管理员 Moonoshawott 禁言 2 小时* > **hjw 18:45:43** >   [幽灵] > **ZC 18:45:47** >   [幽灵] > **Moonoshawott 18:45:53** >   [幽灵] > **henry_y 18:45:54** >   [幽灵] #### 题目信息 * Idea / Std: @[cutekibry](https://loj.ac/user/1408) * Data: @[cutekibry](https://loj.ac/user/1408) / @[hjw](https://loj.ac/user/1206) * Solution: @[moonoshawott](https://loj.ac/user/10399) * Testing: @[moonoshawott](https://loj.ac/user/10399) / @[hjw](https://loj.ac/user/1206) 提示：此题有在线做法。