AdditionalFile3256.zip

P6881 [JOI 2020 Final] 火灾 / Fire

题目背景

原题测试点配置信息：

Subtask 1 (1): 01-*, 02-*, sample-*
Subtask 2 (6): 01-*, 04-*, sample-04
Subtask 3 (7): 01-*, 05-*, sample-03
Subtask 4 (6): 06-*, sample-05
Subtask 5 (80): *

题目描述

给定一个长为 $N$ 的序列 $S_i$，刚开始为时刻 $0$。

定义 $t$ 时刻第 $i$ 个数为 $S_i(t)$，那么：

$$\begin{cases} S_0(t)=0\\S_i(0)=S_i\\S_i(t)=\max\{S_{i-1}(t-1),S_i(t-1)\} \end{cases}$$

你将对 $Q$ 个操作进行评估，第 $j$ 个操作让时刻 $T_j$ 时的区间 $[L_j,R_j]$ 全部变为 $0$。

执行一个操作需要一定的代价，执行第 $j$ 个操作需要以下的代价：

$$\sum\limits_{k=L_j}^{R_j}S_k(T_j)$$

求每个操作需要的代价。

注意：每个操作都是独立的。

输入格式

第一行两个整数 $N,Q$ 代表序列长度和操作数。
第二行 $N$ 个整数 $S_i$ 代表这个序列。
接下来 $Q$ 行每行三个整数 $T_j,L_j,R_j$ 代表一个操作。

输出格式

$Q$ 行每行一个整数代表这个操作需要的代价。

输入输出样例 #1

输入 #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

输入输出样例 #2

输入 #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

输入输出样例 #3

输入 #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

输入输出样例 #4

输入 #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

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

说明/提示

样例 1 解释

• $S_i(0)=\{9,3,2,6,5\}$。
• $S_i(1)=\{9,9,3,6,6\}$，第一个操作需要的代价为 $9+9+3=21$。
• $S_i(2)=\{9,9,9,6,6\}$，第二个操作需要的代价为 $9+9+9+6+6=39$。
• $S_i(3)=\{9,9,9,9,6\}$，第三个操作需要的代价为 $9+9+9+9+6=33$。
• $S_i(4)=\{9,9,9,9,9\}$，第四个操作需要的代价为 $9$。
• $S_i(5)=\{9,9,9,9,9\}$，第五个操作需要的代价为 $27$。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（1 pts）：$N,Q \le 200$。
• Subtask 2（6 pts）：$T_j$ 互相相等。
• Subtask 3（7 pts）：$L_j=R_j$。
• Subtask 4（6 pts）：$S_i \le 2$。
• Subtask 5（80 pts）：无特殊限制。

对于 $100\%$ 的数据：

• $1 \le N \le 2 \times 10^5$。
• $1 \le Q \le 2 \times 10^5$。
• $1 \le S_i \le 10^9$。
• $1 \le T_j \le N$。
• $1 \le L_j \le R_j \le N$。

说明

翻译自 第19回日本情報オリンピック　本選 E 火事。

#3256. 「JOI 2020 Final」火灾

标签: 传统 | 时间限制: 1500 ms | 内存限制: 256 MiB |

题目描述

译自 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

输出

21
39
33
9
27

• 时刻 $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

输出

28
21
34
4
64
43
55
9
27
9

该样例满足子任务 $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

输出

9
9
3
4
3
4
5
9
9
9

该样例满足子任务 $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

输出

28
27
34
4
64
43
55
9
27
9

该样例满足子任务 $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

输出

25
30
12
32
2
24
38
10
14
40
8
28
24
32
4
2
28
28
12
40

该样例满足子任务 $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$