分数: 466 分
问题陈述
高桥管理 N 花坛水平排列。每个花坛的编号为 1 to N和花坛 i 最初存储 C_i 升水。
高桥将表演 Q 操作按顺序进行。每个操作都是在所有先前操作产生的状态上执行的。有 2 操作类型:
- 操作 1 (浇水):
1 l r v— 添加 v 每个花坛的升水量为 l to r,包括在内。 - 操作 2 (查询):
2 l r- 输出所有花坛储存的水总量,数字为 l to r,包括在内。
查找所有操作的答案 2 按给出的顺序进行查询。
约束
- 1 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- 0 \leq C_i \leq 10^4 (1 \leq i \leq N)
- 用于操作 1, 1 \leq l \leq r \leq N 和 1 \leq v \leq 10^4
- 用于操作 2, 1 \leq l \leq r \leq N
- 至少一项操作 给出 2 被给予
- 所有输入值均为整数
- 保证每个操作的答案 2 介于 0 和 2^{63} - 1 (有符号的最大值 64位整数),包括在内
输入
N Q
C_1 C_2 \ldots C_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
每个 \text{query}_j (1 \leq j \leq Q) 采用以下格式之一给出:
1 l r v
2 l r
- 第一行包含一个整数 N 代表花坛数量和一个整数 Q 代表操作次数,以空格分隔。
- 第二行包含整数 C_1, C_2, \ldots, C_N 代表每个花坛的初始水量,以空格分隔。
- 以下各项 Q 行包含一项操作。
- 用于操作 1,以格式给出
1 l r v,包括 4 以空格分隔的整数:操作类型,左端点 l 范围的右端点 r 的范围和水量 v 添加。 范围的 - 用于操作 2,以格式给出
2 l r,包括 3 以空格分隔的整数:操作类型,左端点 l 和右端点 范围的 r 。
输出
每次操作 给定 2 ,输出花坛中储存的水总量,数字为 l to r,包含在该时间点的单行上。按照给出的操作顺序输出结果。
示例输入 1
5 4 3 1 4 1 5 2 1 5 1 2 4 3 2 2 4 2 1 5
示例输出 1
14 15 23
示例输入 2
8 7 2 5 3 7 1 4 6 2 2 1 8 1 3 6 2 2 3 6 1 1 4 5 2 2 7 1 5 8 1 2 1 8
示例输出 2
30 23 49 62
示例输入 3
10 10 10 20 30 40 50 60 70 80 90 100 2 1 10 1 1 5 10 2 1 5 2 6 10 1 3 8 20 2 1 10 1 1 10 5 2 1 10 2 5 5 2 1 1
示例输出 3
550 200 400 720 770 85 25