题目描述
已知一个序列 $a$ 和一个初值为 $0$ 的序列 $b$，你需要进行下面三种操作：
1 x y：将 $a_x$ 修改为 $y$。2 l r：对于所有的 $i \in [l, r]$，将 $b_i$ 加上 $\max_{j=l}^{i} a_j$。3 l r：求 $\sum_{i=l}^{r} b_i$。
输入格式
第一行包含两个正整数 $n, m$，分别表示序列 $a$ 的长度和操作次数。
第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$，表示序列 $a$。
接下来 $m$ 行，每行行首有一个整数 $op$，表示操作类型，接下来两个整数表示操作参数。
输出格式
对于 $op = 3$ 的操作，输出一行包含一个整数，表示这个询问的答案。
样例输入 1
5 5 2 1 4 3 5 2 1 3 2 4 3 1 2 3 3 1 3 3 2 5
样例输出 1
8 6
样例输入 2
10 10 5 6 10 3 6 7 10 10 1 10 2 2 4 1 10 7 3 2 8 2 4 5 1 8 2 3 2 2 2 8 9 2 1 2 1 2 10 3 2 3
样例输出 2
26 6 22
数据范围
对于 $100\%$ 的数据，保证 $1 \le n, m \le 5 \times 10^5$， $1 \le l \le r \le n$，$1 \le x \le n$，$1 \le a_i, y \le 10^9$。
| 子任务编号 | $n, m \le$ | 分值 | 特殊性质 |
|---|---|---|---|
| $1$ | $1000$ | $5$ | 无 |
| $2$ | $10^5$ | $15$ | |
| $3$ | $2 \times 10^5$ | $20$ | |
| $4$ | $5 \times 10^5$ | $20$ | 当 $op = 2$ 时，$l = 1$。 |
| $5$ | $20$ | $op \ne 1$ | |
| $6$ | $20$ | 无 |