T265439 lhy的气焰值

`C2024XSC700` 发现：在初一 `lhy` 带的信竞课上，总是会有人脱控（比如使用任务管理器和极域拜拜）,于是 `lhy` 就因为学生的脱控而拥有一个气焰值。而 `lhy` 的学生就会因为`lhy` 的生气而有了一个开心值。

由于每个人（包括 `lhy` ）因为生来就与众不同，所以每个学生生来就有一个开心值，`lhy` 便有一个气焰值。

第 $1$ 行，两个数字 $n,q$ 代表一共有 $n$ 个人（`lhy` 的编号为 $1$，学生编号 $2 \sim n$），$q$ 次脱控或查询。 第 $2$ 行，$n$ 个数字 $a_1,a_2,a_3,\cdots,a_n$，代表每个人最开始的值。 第 $3 - m + 2$ 行，每行表示每次脱控的信息。 首先，每行第一个数 $f\in[1,3]$。 当 $f = 1$ 时，再输入三个整数 $l,r,v$，表示有 $v$ 个人脱控，将引起 `lhy` 的愤怒值 $+v$，编号在 $[l,r]$ 学生开心值 $+\left\lfloor\displaystyle\frac v 2\right\rfloor$。 当 $f = 2$ 时，表示查询 `lhy` 的愤怒值。 当 $f = 3$ 时，再输入两个整数 $l,r$，表示查询编号在 $[l,r]$ 学生的值总和。

每行输出一个值，表示 $f = 2$ 或 $3$ 时询问的答案。

样例组 $1$ 满足 $\text{Subtask}\ 1$ 的限制。 样例组 $2$ (见附件中 $\text{ans2.in}$ 与 $\text{ans2.out}$ ) 满足 $\text{Subtask}\ 3$ 的限制。 样例组 $3$ (见附件中 $\text{ans3.in}$ 与 $\text{ans3.out}$ ) 满足 $\text{Subtask}\ 4$ 的限制。 样例组 $4$ (见附件中 $\text{ans4.in}$ 与 $\text{ans4.out}$ ) 满足 $\text{Subtask}\ 7$ 的限制。 性质 $1$：$v$ 为偶数。 性质 $2$：没有 $f = 2$ 的询问 性质 $3$：没有 $f = 3$ 的询问 性质 $4$：$a_i,v \leq 10^3\ (1\le i\le n)$ 性质 $5$：数据随机生成 | 子任务| 测试点 | 分值 | $n,q \leq$ | 满足性质 | | :----------: | :----------: | :----------: | :----------: |:----------: | | $\text{Subtask 1}$ |$1 \sim 3$| $6$ | $20$ | $4,5$| | $\text{Subtask 2}$ |$4 \sim 5$| $4$ | $50$ | $5$| | $\text{Subtask 3}$ |$6 \sim 7$| $8$ | $5\times 10^2$ |$1,4,5$ | | $\text{Subtask 4}$ |$8 \sim 10$| $12$ | $10 ^3$ | $5$| | $\text{Subtask 5}$ |$11 \sim 14$| $20$ | $5\times 10^3$ | $5$ | | $\text{Subtask 6}$ |$15$| $5$ | $5\times 10^4$ | $3,5$ | | $\text{Subtask 7}$ |$16 \sim 18$| $15$ | $5\times 10^4$ | 无 | | $\text{Subtask 8}$ |$19$| $5$ | $2\times 10^5$ | $2,5$ | | $\text{Subtask 9}$ |$20 \sim 22$| $15$ | $2\times 10^5$ | 无 | | $\text{Subtask 10}$ |$23 \sim 25$| $10$ | $5\times 10^5$ | 无 | 对于 $100\%$ 的数据，$1\leq n,m\leq5\times 10^5$，$1\leq v,a_i \leq 10^6$，$1 \leq l,r \leq n$。 注：每一组数据均绑点，数据有梯度，且本题每个测试点时限均在 $\text{std}$ 的 $1.2$ 倍以上。 **注意事项：** 1. 输入输出速度。 1. 提交的语言与 $\text{O}2$ 对时间上的影响 1. 数据类型的使用对答案正确性上的影响