← 返回题目列表

AtCoder · joi2020ho_e

E. 火

中文机器翻译题面 查看原题

配点: 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. (1 点) N \leqq 200,Q \leqq 200.
  2. (6 点) T_1 = T_2 = \cdots = T_Q.
  3. (7 点) L_j = R_j (1 \leqq j \leqq Q).
  4. (6 点) S_i \leqq 2 (1 \leqq i \leqq N).
  5. (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 满足约束。