3359 - 扶苏的问题
时间限制 : 4 秒
内存限制 : 512 MB
给定⼀个长度为 n 的序列 a，要求⽀持如下三个操作：
- 给定区间 [l, r]，将区间内每个数都修改为 x。
- 给定区间 [l, r]，将区间内每个数都加上 x。
- 给定区间 [l, r]，求区间内的最⼤值。
输入
第⼀⾏是两个整数，依次表⽰序列的长度 n 和操作的个数 q。
第⼆⾏有 n 个整数，第 i 个整数表⽰序列中的第 i 个数 ai。
接下来 q ⾏，每⾏表⽰⼀个操作。每⾏⾸先有⼀个整数 op，表⽰操作的类型。
若 op = 1， 则接下来有三个整数 l, r, x ，表⽰将区间 [l, r] 内的每个数都修改为 x。
若 op = 2， 则接下来有三个整数 l, r, x ，表⽰将区间 [l, r] 内的每个数都加上 x。
若 op = 3， 则接下来有两个整数 l, r，表⽰查询区间 [l, r] 内的最⼤值。
输出
对于每个 op = 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 的数据， n = q = 1。
· 对于 40 的数据， n, q ≤ 10^3。
· 对于 50 的数据， 0 ≤ ai , x ≤ 10^4 。
· 对于 60 的数据， op ≠ 1。
· 对于 90 的数据， n, q ≤ 10^5。
· 对于 100 的数据， 1 ≤ n, q ≤ 10^6， 1 ≤ l, r ≤ n， op ∈ 1, 2, 3， |ai |, |x| ≤ 10^9。