P1253 扶苏的问题
题目描述
给定一个长度为 n 的序列 {a1,a2,…,an},需要支持以下三种操作:
1.给定区间 [l,r] 和整数 x,将区间内的每个数都修改为 x;
2.给定区间 [l,r] 和整数 x,将区间内的每个数都加上 x;
3.给定区间 [l,r],求出区间内所有数的最大值。
输入格式
第一行输入两个整数 n,q(1≦n,q≦106) 分别代表序列的长度和操作的个数。
第二行输入 n 个整数 $a_1, a_2, \dots, a_n \left(-10^9 \leqq a_i \leqq 10^9\right)$ 代表序列中的元素。
此后 q 行,第 i 行先输入一个整数 $\mathrm{op}_i \left(1 \leqq \mathrm{op}_i \leqq 3\right)$ 代表操作类型,随后在同一行上:
∙若 opi=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] 内的每个数都修改为 xi;
∙若 opi=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] 内的每个数都加上 xi;
∙若 opi=3,输入两个整数 $l_i, r_i \left(1 \leqq l_i \leqq r_i \leqq n\right)$,代表查询区间 [li,ri] 内的最大值。
输出格式
对于每个 opi=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 解释
初始时,序列为 {1,1,4,5,1,4}。
∙第一次操作将区间 [1,2] 内的每个数修改为 6,序列变为 {6,6,4,5,1,4};
∙第二次操作将区间 [3,4] 内的每个数加上 2,序列变为 {6,6,6,7,1,4};
∙第三次操作查询区间 [1,4] 的最大值,得到 7;
∙第四次操作查询区间 [2,3] 的最大值,得到 6;
∙第五次操作将区间 [1,6] 内的每个数修改为 −1,序列变为 {−1,−1,−1,−1,−1,−1};
∙第六次操作查询区间 [1,6] 的最大值,得到 −1。
4 4
10 4 -3 -7
1 1 3 0
2 3 4 -4
1 2 4 -9
3 1 4
0
样例 2 解释
初始时,序列为 {10,4,−3,−7}。
∙第一次操作将区间 [1,3] 内的每个数修改为 0,序列变为 {0,0,0,−7};
∙第二次操作将区间 [3,4] 内的每个数加上 −4,序列变为 {0,0,−4,−11};
∙第三次操作将区间 [2,4] 内的每个数修改为 −9,序列变为 {0,−9,−9,−9};
∙第四次操作查询区间 [1,4] 的最大值,得到 0。
提示
本题各子任务的分数与数据范围如下:
∙对于 10% 的数据,n=q=1;
∙对于 40% 的数据,n,q≦103;
∙对于 50% 的数据,0≦ai,x≦104;
∙对于 60% 的数据,op=1;
∙对于 90% 的数据,n,q≦105;
∙对于 100% 的数据,1≦n,q≦106,1≦l≦r≦n,op∈{1,2,3},∣ai∣,∣x∣≦109。
请注意大量数据读入对程序效率造成的影响。