【模板】线段树 3(区间最值操作、区间历史最值)
题目背景
本题是线段树维护区间最值操作与区间历史最值的模板。
题目描述
给出一个长度为 $n$ 的数列 $A$,同时定义一个辅助数组 $B$,$B$ 开始与 $A$ 完全相同。接下来进行了 $m$ 次操作,操作有五种类型,按以下格式给出:
- `1 l r k`:对于所有的 $i\in[l,r]$,将 $A_i$ 加上 $k$($k$ 可以为负数)。
- `2 l r v`:对于所有的 $i\in[l,r]$,将 $A_i$ 变成 $\min(A_i,v)$。
- `3 l r`:求 $\sum_{i=l}^{r}A_i$。
- `4 l r`:对于所有的 $i\in[l,r]$,求 $A_i$ 的最大值。
- `5 l r`:对于所有的 $i\in[l,r]$,求 $B_i$ 的最大值。
在每一次操作后,我们都进行一次更新,让 $B_i\gets\max(B_i,A_i)$。
输入输出格式
输入格式
第一行包含两个正整数 $n,m$,分别表示数列 $A$ 的长度和操作次数。
第二行包含 $n$ 个整数 $A_1,A_2,\cdots,A_n$,表示数列 $A$。
接下来 $m$ 行,每行行首有一个整数 $op$,表示操作类型;接下来两个或三个整数表示操作参数,格式见【题目描述】。
输出格式
对于 $op\in\{3,4,5\}$ 的操作,输出一行包含一个整数,表示这个询问的答案。
输入输出样例
输入样例 #1
5 6
1 2 3 4 5
3 2 5
1 1 3 3
4 2 4
2 3 4 1
5 1 5
3 1 4
输出样例 #1
14
6
6
11
说明
#### 样例说明 \#1 ####
| 操作次数 | 输入内容 | 操作 | 数列 | 输出结果 |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| 0 | | | $1,2,3,4,5$ | |
| 1 | `3 2 5` | 求出 $[2,5]$ 所有数的和 | $1,2,3,4,5$ | `14` |
| 2 | `1 1 3 3` | 将 $[1,3]$ 内所有数加 $3$ | $4,5,6,4,5$ | |
| 3 | `4 2 4` | 求出 $[2,4]$ 所有数的最大值 | $4,5,6,4,5$ | `6` |
| 4 | `2 3 4 1` | 将 $[3,4]$ 所有数与 $1$ 取最小值 | $4,5,1,1,5$ | |
| 5 | `5 1 5` | 求出 $[1,5]$ 所有位置历史最大值的最大值 | $4,5,1,1,5$ | `6` |
| 6 | `3 1 4` | 求出 $[1,4]$ 所有数的和 | $4,5,1,1,5$ | `11` |
#### 数据规模与约定
- 对于测试点 $1,2$,满足 $n,m\leq 5000$;
- 对于测试点 $3,4$,满足 $op\in\{1,2,3,4\}$;
- 对于测试点 $5,6$,满足 $op\in\{1,3,4,5\}$;
- 对于全部测试数据,保证 $1\leq n,m\leq 5\times 10^5$,$-5\times10^8\leq A_i\leq 5\times10^8$,$op\in[1,5]$,$1 \leq l\leq r \leq n$,$-2000\leq k\leq 2000$,$-5\times10^8\leq v\leq 5\times10^8$。
#### 提示 ####
本题输入量较大,请使用合理高效的读入方法。