#6727. 「hyOI2020」henry_y 的数列

内存限制:256 MiB 时间限制:1500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: cutekibry

题目描述

给出一个长度为 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

样例解释

操作参数 意义 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
  [幽灵]

题目信息