配点: 100 点
在JOI村 有 N 分区, 它们的编号最大为1 它们的编号最大为 N 。这些隔间按数字顺序排列成一排。目前,各路段均发生火灾,时间 在 0 中分区 火势为 i (1 \leqq i \leqq N) S_i (S_i > 0)。
時刻 0 ,分区 从 1 分区 风开始朝 N 方向吹。彼此相邻 2 对于一个分区,时间 t (0 \leqq t),当迎风舱火灾强于背风舱火灾时,时间 t + 1 处背风段的火灾强度由时间决定 火灾强度与 t 中迎风部分的火灾强度相同。不然时间 与 t + 1 处背风段的火灾强度由时间决定 火灾强度与 t 相同。换句话说,时间 t (0 \leqq t) i (1 \leqq i \leqq N) 防火强度 如果我们写 S_i(t) ,1 \leqq t 然后,S_i(t) = \max\{S_{i − 1}(t − 1), S_i(t − 1)\} 变为。然而,任何 t (0 \leqq t),S_0(t) = 0 和任何 i (1 \leqq i \leqq N)对于 S_i(0) = S_i 。
你是一名消防员。 Q 已计划开展消防行动。 哪个Q 计划 1 我们计划仅实施一项。j 第计划(1 \leqq j \leqq Q) 是时间 T_j , 所有L_j \leqq k \leqq R_j 的分区 k 通过分配灭火剂并扑灭这些部分。火的强度 熄灭 s 的部分 s 需要几升灭火剂。换句话说,j 对于第二个计划的消防行动, S_{L_j}(T_j) + S_{L_j + 1}(T_j) + \cdots + S_{R_j}(T_j) 需要几升灭火剂。
为了仔细考虑实施哪个计划,我想知道每个计划所需的灭火剂用量。 根据
時刻 0 中有关火灾强度和消防活动计划的信息,编写一个程序来计算每个计划所需的灭火剂数量。
入力
输入是按以下格式从标准输入给出的。所有输入值都是整数。
N Q S_1 \cdots S_N T_1 L_1 R_1 \vdots T_Q L_Q R_Q
出力
到标准输出 输出为 Q 行。不。 j 行目 (1 \leqq j \leqq Q) 是 j 输出计划所需的灭火剂用量。
制約
- 1 \leqq N \leqq 200\,000.
- 1 \leqq Q \leqq 200\,000.
- 1 \leqq S_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N).
- 1 \leqq T_j \leqq N (1 \leqq j \leqq Q).
- 1 \leqq L_j \leqq R_j \leqq N (1 \leqq j \leqq Q).
小課題
- (1 点) N \leqq 200,Q \leqq 200.
- (6 点) T_1 = T_2 = \cdots = T_Q.
- (7 点) L_j = R_j (1 \leqq j \leqq Q).
- (6 点) S_i \leqq 2 (1 \leqq i \leqq N).
- (80 点)没有额外的限制。
入力例 1
5 5 9 3 2 6 5 1 1 3 2 1 5 3 2 5 4 3 3 5 3 5
出力例 1
21 39 33 9 27
- 時刻 0 中每个隔间的火灾强度为 从 1 开始 9, 3, 2, 6, 5 。从
- 時刻 1 中每个隔间的火灾强度为 从 1 开始 9, 9, 3, 6, 6 。因此,1 计划所需的灭火剂用量为 9 + 9 + 3 = 21 是升。
- 時刻 2 中每个隔间的火灾强度为 从 1 开始 9, 9, 9, 6, 6 。因此,2 计划所需的灭火剂用量为 9 + 9 + 9 + 6 + 6 = 39 是升。
- 時刻 3 中每个隔间的火灾强度为 从 1 开始 9, 9, 9, 9, 6 。因此,3 计划所需的灭火剂用量为 9 + 9 + 9 + 6 = 33 是升。
- 時刻 4 中每个隔间的火灾强度为 从 1 开始 9, 9, 9, 9, 9 。因此,4 计划所需的灭火剂用量为 9 是升。
- 時刻 5 中每个隔间的火灾强度为 从 1 开始 9, 9, 9, 9, 9 。因此,5 计划所需的灭火剂用量为 9 + 9 + 9 = 27 是升。
入力例 1 是一个小作业 1, 5 满足约束。
入力例 2
10 10 3 1 4 1 5 9 2 6 5 3 1 1 6 2 8 10 4 2 7 8 3 3 6 1 10 3 2 8 5 1 9 7 4 5 9 7 9 10 10 10
出力例 2
28 21 34 4 64 43 55 9 27 9
入力例 2 是一个小作业 1, 5 满足约束。
入力例 3
10 10 3 1 4 1 5 9 2 6 5 3 1 6 6 2 8 8 4 2 2 8 3 3 6 1 1 3 4 4 5 5 5 7 10 10 9 8 8 10 7 7
出力例 3
9 9 3 4 3 4 5 9 9 9
入力例 3 是一个小作业 1, 3, 5 满足约束。
入力例 4
10 10 3 1 4 1 5 9 2 6 5 3 7 1 6 7 8 10 7 2 7 7 3 3 7 1 10 7 2 8 7 1 9 7 4 5 7 7 9 7 10 10
出力例 4
28 27 34 4 64 43 55 9 27 9
入力例 4 是一个小作业 1, 2, 5 满足约束。
入力例 5
20 20 2 1 2 2 1 1 1 1 2 2 2 1 2 1 1 2 1 2 1 1 1 1 14 2 3 18 4 10 15 8 2 17 9 20 20 4 8 19 7 2 20 11 1 5 13 2 8 20 1 20 2 12 15 7 1 14 12 7 18 14 2 17 9 19 20 12 12 12 6 2 15 11 2 15 19 12 17 4 1 20
出力例 5
25 30 12 32 2 24 38 10 14 40 8 28 24 32 4 2 28 28 12 40
入力例 5 是一个小作业 1, 4, 5 满足约束。