[yLOI2018] 扶苏的问题

题目描述

给定一个长度为 $n$ 的序列 $a$,要求支持如下三个操作: 1. 给定区间 $[l, r]$,将区间内每个数都修改为 $x$。 2. 给定区间 $[l, r]$,将区间内每个数都加上 $x$。 3. 给定区间 $[l, r]$,求区间内的最大值。

输入输出格式

输入格式


第一行是两个整数,依次表示序列的长度 $n$ 和操作的个数 $q$。 第二行有 $n$ 个整数,第 $i$ 个整数表示序列中的第 $i$ 个数 $a_i$。 接下来 $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$ 的操作,输出一行一个整数表示答案。

输入输出样例

输入样例 #1

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

输出样例 #1

7
6
-1

输入样例 #2

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

输出样例 #2

0

说明

### 数据规模与约定 - 对于 $10\%$ 的数据,$n = q = 1$。 - 对于 $40\%$ 的数据,$n, q \leq 10^3$。 - 对于 $50\%$ 的数据,$0 \leq a_i, x \leq 10^4$。 - 对于 $60\%$ 的数据,$op \neq 1$。 - 对于 $90\%$ 的数据,$n, q \leq 10^5$。 - 对于 $100\%$ 的数据,$1 \leq n, q \leq 10^6$,$1 \leq l, r \leq n$,$op \in \{1, 2, 3\}$,$|a_i|, |x| \leq 10^9$。 ### 提示 请注意大量数据读入对程序效率造成的影响。