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 解释 - $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)。