题目描述

给出一个长度为 $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$ 行，每行三到五个整数，描述操作。

输出格式

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

5 6
2 2 5 3 5
1 1 5 0 3 0
1 2 3 1 0 1
2 2 4
1 1 5 0 2 3
1 1 5 2 1 1
2 3 4

13
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$。

本题采用子任务评测。对于同个子任务，你只有通过该子任务内的所有测试点，才能拿到该子任务的分数。

关于「数据有一定程度的随机」的解释：该子任务内所有数据由以下方式生成。

• 首先手动决定 $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:
  https://loj.ac/user/1408
• Data:
  https://loj.ac/user/1408
  w](https://loj.ac/user/1206)
• Solution:
  https://loj.ac/user/10399
• Testing:
  https://loj.ac/user/10399
  https://loj.ac/user/1206)