#3256. 「JOI 2020 Final」火灾

内存限制:256 MiB 时间限制:1500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: ksyx

题目描述

译自 JOI 2020 Final T5「火事 / Fire

在 JOI 世界里有 N 个地区排成一条线。为了方便,我们将这些地区编号为 1 N 。突然,各个地区都起火了。在时刻 0 ,第 i 个区的火势大小为 S_i

此时(时刻 0 ),一阵风从 1 号地区一直吹到了 N 号地区。对于每两个相邻的地区,如果 t 时刻上风地区的火势比下风地区的强, t+1 时刻下风地区的火势大小将变为 t 时刻上风地区的火势,否则 t+1 t 时刻时下风地区的火势大小不变。
形式化地说,如果 t 时刻 i 地区的火势为 S_i(t) ,则 S_i(t)=\max\{S_{i-1}(t-1),S_i(t-1)\} ,其中 S_0(t)=0,~S_i(0)=S_i

你是一位消防员。现在,你想到了 Q 种灭火方案,并打算执行其中一种。你的第 j 种方案是在 T_j 时刻对 [L_j,~R_j] 中的所有地区使用灭火剂完全扑灭火灾。
对于一个火势大小为 s 的城市,你将需要 s 升的灭火剂来扑灭火灾。因此,执行方案 j 总共要花费 S_{L_j}(T_j)+S_{L_j+1}(T_j)+\cdots +S_{R_j}(T_j) 升灭火剂。
译者注:英文版题面中没有定义 T_j ,此处定义从日文版中提取。

为了更好地选取灭火方案,你的任务是编写一个程序,给出 0 时刻的火势大小,计算各个方案所需的灭火剂量。

输入格式

第一行两个数 N,~Q ,含义如题面所示。
接下来一行 N 个数 S_1\dots S_N ,表示初始时的火势大小。
接下来 Q 行每行三个数 T_j,~L_j,~R_j ,表示方案 j 的相关信息。

输出格式

输出 Q 行,第 i 行表示方案 j 所需的灭火剂量。

样例

样例输入 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

样例解释 1

  • 时刻 0 时地区 1 到 地区 N 的火势大小分别为 9,~3,~2,~6,~5
  • 时刻 1 时地区 1 到 地区 N 的火势大小分别为 9,~9,~3,~6,~6 。方案 1 需要的灭火剂量为 9+9+3=21 升。
  • 时刻 2 时地区 1 到 地区 N 的火势大小分别为 9,~9,~9,~6,~6 。方案 2 需要的灭火剂量为 9+9+9+6+6=39 升。
  • 时刻 3 时地区 1 到 地区 N 的火势大小分别为 9,~9,~9,~9,~6 。方案 3 需要的灭火剂量为 9+9+9+6=33 升。
  • 时刻 4 时地区 1 到 地区 N 的火势大小分别为 9,~9,~9,~9,~9 。方案 4 需要的灭火剂量为 9 升。
  • 时刻 5 时地区 1 到 地区 N 的火势大小分别为 9,~9,~9,~9,~9 。方案 5 需要的灭火剂量为 9+9+9=27 升。

该样例满足子任务 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 的限制。

数据范围与提示

对于所有测试数据 1\le N,Q\le 2\times 10^5,~1\le S_i\le 10^9,~1\le L_j,~R_j,~T_j\le N

子任务编号 分值 具体限制
1 1 1 \le N,Q \le 200
2 6 T_1 = T_2 = \ldots = T_Q
3 7 L_j = R_j\ (1 \le j \le Q)
4 6 S_i \le 2\ (1 \le i \le N)
5 80