[JOI 2020 Final] 火事

因为数据包过大，所以本题只测试 Subtask 4 & 5。 Subtask 1 & 2 & 3 请在 [这里](https://www.luogu.com.cn/problem/U132672) 测试。

给定一个长为 $N$ 的序列 $S_i$，刚开始为时刻 $0$。 定义 $t$ 时刻第 $i$ 个数为 $S_i(t)$，那么： $$\left\{ \begin{array}{ll} S_0(t)=0\\S_i(0)=S_i\\S_i(t)=\max\{S_{i-1}(t-1),S_i(t-1)\} \end{array} \right.$$ 你将对 $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$ 行每行一个整数代表这个操作需要的代价。

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

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

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

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

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 解释 - $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回日本情報オリンピック　本選](https://www.ioi-jp.org/joi/2019/2020-ho/index.html) [E 火事](https://www.ioi-jp.org/joi/2019/2020-ho/2020-ho-t5.pdf)。