luogu#P1253. 扶苏的问题

扶苏的问题

题目描述

给定一个长度为 nn 的序列 aa,要求支持如下三个操作:

  1. 给定区间 [l,r][l, r],将区间内每个数都修改为 xx
  2. 给定区间 [l,r][l, r],将区间内每个数都加上 xx
  3. 给定区间 [l,r][l, r],求区间内的最大值。

输入格式

第一行是两个整数,依次表示序列的长度 nn 和操作的个数 qq
第二行有 nn 个整数,第 ii 个整数表示序列中的第 ii 个数 aia_i
接下来 qq 行,每行表示一个操作。每行首先有一个整数 opop,表示操作的类型。

  • op=1op = 1,则接下来有三个整数 l,r,xl, r, x,表示将区间 [l,r][l, r] 内的每个数都修改为 xx
  • op=2op = 2,则接下来有三个整数 l,r,xl, r, x,表示将区间 [l,r][l, r] 内的每个数都加上 xx
  • op=3op = 3,则接下来有两个整数 l,rl, r,表示查询区间 [l,r][l, r] 内的最大值。

输出格式

对于每个 op=3op = 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
4 4
10 4 -3 -7
1 1 3 0
2 3 4 -4
1 2 4 -9
3 1 4
0

提示

数据规模与约定

  • 对于 10%10\% 的数据,n=q=1n = q = 1
  • 对于 40%40\% 的数据,n,q103n, q \leq 10^3
  • 对于 50%50\% 的数据,0ai,x1040 \leq a_i, x \leq 10^4
  • 对于 60%60\% 的数据,op1op \neq 1
  • 对于 90%90\% 的数据,n,q105n, q \leq 10^5
  • 对于 100%100\% 的数据,1n,q1061 \leq n, q \leq 10^61l,rn1 \leq l, r \leq nop{1,2,3}op \in \{1, 2, 3\}ai,x109|a_i|, |x| \leq 10^9

提示

请注意大量数据读入对程序效率造成的影响。