P6242 【模板】线段树 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

输入 #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

数据规模与约定

• 对于测试点 $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$。

提示

本题输入量较大，请使用合理高效的读入方法。