LG#P1253. 扶苏的问题

扶苏的问题

P1253 扶苏的问题

题目描述

\hspace{15pt}给定一个长度为 nn 的序列 {a1,a2,…,an}\{a_1, a_2, \dots, a_n\},需要支持以下三种操作:

1. {\hspace{20pt}}_\texttt{1.}\,给定区间 [l,r][l, r] 和整数 xx,将区间内的每个数都修改为 xx;

2. {\hspace{20pt}}_\texttt{2.}\,给定区间 [l,r][l, r] 和整数 xx,将区间内的每个数都加上 xx;

3. {\hspace{20pt}}_\texttt{3.}\,给定区间 [l,r][l, r],求出区间内所有数的最大值。

输入格式

\hspace{15pt}第一行输入两个整数 n,q(1≦n,q≦106)n, q \left(1 \leqq n, q \leqq 10^6\right) 分别代表序列的长度和操作的个数。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(-10^9 \leqq a_i \leqq 10^9\right)$ 代表序列中的元素。

\hspace{15pt}此后 qq 行,第 ii 行先输入一个整数 $\mathrm{op}_i \left(1 \leqq \mathrm{op}_i \leqq 3\right)$ 代表操作类型,随后在同一行上:

∙ \hspace{23pt}\bullet\,若 opi=1\mathrm{op}_i = 1,输入三个整数 $l_i, r_i, x_i \left(1 \leqq l_i \leqq r_i \leqq n;\ -10^9 \leqq x_i \leqq 10^9\right)$,代表将区间 [li,ri][l_i, r_i] 内的每个数都修改为 xix_i;

∙ \hspace{23pt}\bullet\,若 opi=2\mathrm{op}_i = 2,输入三个整数 $l_i, r_i, x_i \left(1 \leqq l_i \leqq r_i \leqq n;\ -10^9 \leqq x_i \leqq 10^9\right)$,代表将区间 [li,ri][l_i, r_i] 内的每个数都加上 xix_i;

∙ \hspace{23pt}\bullet\,若 opi=3\mathrm{op}_i = 3,输入两个整数 $l_i, r_i \left(1 \leqq l_i \leqq r_i \leqq n\right)$,代表查询区间 [li,ri][l_i, r_i] 内的最大值。

输出格式

\hspace{15pt}对于每个 opi=3\mathrm{op}_i = 3 的操作,新起一行输出一个整数,代表该次查询的区间最大值。

测试样例

6 6
1 1 4 5 1 4
1 1 2 6
2 3 4 2
3 1 4
3 2 3
1 1 6 -1
3 1 6
7
6
-1

样例 1 解释

\hspace{15pt}初始时,序列为 {1,1,4,5,1,4}\{1, 1, 4, 5, 1, 4\}。

∙ \hspace{23pt}\bullet\,第一次操作将区间 [1,2][1, 2] 内的每个数修改为 66,序列变为 {6,6,4,5,1,4}\{6, 6, 4, 5, 1, 4\};

∙ \hspace{23pt}\bullet\,第二次操作将区间 [3,4][3, 4] 内的每个数加上 22,序列变为 {6,6,6,7,1,4}\{6, 6, 6, 7, 1, 4\};

∙ \hspace{23pt}\bullet\,第三次操作查询区间 [1,4][1, 4] 的最大值,得到 77;

∙ \hspace{23pt}\bullet\,第四次操作查询区间 [2,3][2, 3] 的最大值,得到 66;

∙ \hspace{23pt}\bullet\,第五次操作将区间 [1,6][1, 6] 内的每个数修改为 −1-1,序列变为 {−1,−1,−1,−1,−1,−1}\{-1, -1, -1, -1, -1, -1\};

∙ \hspace{23pt}\bullet\,第六次操作查询区间 [1,6][1, 6] 的最大值,得到 −1-1。

4 4
10 4 -3 -7
1 1 3 0
2 3 4 -4
1 2 4 -9
3 1 4
0

样例 2 解释

\hspace{15pt}初始时,序列为 {10,4,−3,−7}\{10, 4, -3, -7\}。

∙ \hspace{23pt}\bullet\,第一次操作将区间 [1,3][1, 3] 内的每个数修改为 00,序列变为 {0,0,0,−7}\{0, 0, 0, -7\};

∙ \hspace{23pt}\bullet\,第二次操作将区间 [3,4][3, 4] 内的每个数加上 −4-4,序列变为 {0,0,−4,−11}\{0, 0, -4, -11\};

∙ \hspace{23pt}\bullet\,第三次操作将区间 [2,4][2, 4] 内的每个数修改为 −9-9,序列变为 {0,−9,−9,−9}\{0, -9, -9, -9\};

∙ \hspace{23pt}\bullet\,第四次操作查询区间 [1,4][1, 4] 的最大值,得到 00。

提示

\hspace{15pt}本题各子任务的分数与数据范围如下:

∙ \hspace{23pt}\bullet\,对于 10%10\% 的数据,n=q=1n = q = 1;

∙ \hspace{23pt}\bullet\,对于 40%40\% 的数据,n,q≦103n, q \leqq 10^3;

∙ \hspace{23pt}\bullet\,对于 50%50\% 的数据,0≦ai,x≦1040 \leqq a_i, x \leqq 10^4;

∙ \hspace{23pt}\bullet\,对于 60%60\% 的数据,op≠1\mathrm{op} \neq 1;

∙ \hspace{23pt}\bullet\,对于 90%90\% 的数据,n,q≦105n, q \leqq 10^5;

∙ \hspace{23pt}\bullet\,对于 100%100\% 的数据,1≦n,q≦1061 \leqq n, q \leqq 10^6,1≦l≦r≦n1 \leqq l \leqq r \leqq n,op∈{1,2,3}\mathrm{op} \in \{1, 2, 3\},∣ai∣,∣x∣≦109\left|a_i\right|, \left|x\right| \leqq 10^9。

\hspace{15pt}请注意大量数据读入对程序效率造成的影响。