#1494. 「hyOI2020」henry_y 的数列

「hyOI2020」henry_y 的数列

题目描述

给出一个长度为 nn 的正整数序列 {An}\{A_n\},维护 qq 个操作,操作有两种:

  • 1 l r a b clir,iN\forall l \leq i \leq r, i \in \mathbb{N},令 AiA_i 变为 Ai+ai2+bi+cA_i + ai^2 + bi + c
  • 2 l r:输出 minlir{Ai}\min_{l \leq i \leq r} \{A_i\} 的值。

输入格式

第一行,两个整数 n,qn, q,分别表示序列长度和操作个数。

第二行,nn 个整数 A1,A2,,AnA_1, A_2, \ldots, A_n,表示序列。

接下来 qq 行,每行三到五个整数,描述操作。

输出格式

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

样例

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
操作参数 意义 A1A_1 A2A_2 A3A_3 A4A_4 A5A_5 输出
初始 2 2 5 3 5
1 1 5 0 3 0 [1,5][1, 5] 内的 AiA_i 变为 Ai+3iA_i + 3i 5 8 14 15 20
1 2 3 1 0 1 [2,3][2, 3] 内的 AiA_i 变为 Ai+i2+1A_i + i^2 + 1 5 13 24 15 20
2 2 4 查询 [2,4][2, 4] 内的 AiA_i 的最小值 5 13 24 15 20 13
1 1 5 0 2 3 [1,5][1, 5] 内的 AiA_i 变为 Ai+2i+3A_i + 2i + 3 10 20 33 26 33
1 1 5 2 1 1 [1,5][1, 5] 内的 AiA_i 变为 Ai+2i2+i+1A_i + 2i^2 + i + 1 14 31 55 63 89
2 3 4 查询 [3,4][3, 4] 内的 AiA_i 的最小值 14 31 55 63 89 55

数据范围与提示

对于 100%100\% 的数据,1n,q1051 \leq n, q \leq 10^50Ai,c10130 \leq A_i, c \leq 10^{13}0b1080 \leq b \leq 10^80a1030 \leq a \leq 10^31lrn1 \leq l \leq r \leq n

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

子任务编号 约定 分值
11 n,q8000n, q \leq 8000 1010
22 数据有一定程度的随机 7070
33 询问次数不超过 700700 1010
44 无特殊限制 1010

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

  • 首先手动决定 n,q,X,Y,Zn, q, X, Y, Z 的值,其中 1n,q1051 \leq n, q \leq 10^50X1030 \leq X \leq 10^30Y1080 \leq Y \leq 10^80Z10130 \leq Z \leq 10^{13}
  • 任意 aa 均在 [0,X][0, X] 范围内等概率随机生成,bb[0,Y][0, Y] 范围内等概率随机生成,Ai,cA_i, c[0,Z][0, Z] 范围内等概率随机生成。
  • 对于操作中的区间参数 l,rl, r,生成方式为:
    • 首先等概率随机生成整数 k[1,n]k \in [1, n],表示区间长度;
    • 再等概率随机生成整数 l[1,nk+1]l \in [1, n - k + 1],表示区间的左端点;
    • 计算 r=l+k1r = l + k - 1,表示区间的右端点。

题目信息