P6881 [JOI 2020 Final] Fire / Fire

Original test point configuration information: ``` 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): * ```

You are given a sequence $S_i$ of length $N$, starting at time $0$. Let the $i$-th value at time $t$ be $S_i(t)$. Then: $$\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}$$ You will evaluate $Q$ operations. The $j$-th operation sets all values in the interval $[L_j, R_j]$ at time $T_j$ to $0$. Performing an operation has a cost. The cost of the $j$-th operation is: $$\sum\limits_{k=L_j}^{R_j}S_k(T_j)$$ Compute the cost required for each operation. Note: each operation is independent.

The first line contains two integers $N, Q$, representing the length of the sequence and the number of operations. The second line contains $N$ integers $S_i$, representing the sequence. The next $Q$ lines each contain three integers $T_j, L_j, R_j$, representing one operation.

Output $Q$ lines, each containing one integer, representing the cost required for the corresponding operation.

#### Sample 1 Explanation - $S_i(0)=\{9,3,2,6,5\}$. - $S_i(1)=\{9,9,3,6,6\}$. The cost of the first operation is $9+9+3=21$. - $S_i(2)=\{9,9,9,6,6\}$. The cost of the second operation is $9+9+9+6+6=39$. - $S_i(3)=\{9,9,9,9,6\}$. The cost of the third operation is $9+9+9+9+6=33$. - $S_i(4)=\{9,9,9,9,9\}$. The cost of the fourth operation is $9$. - $S_i(5)=\{9,9,9,9,9\}$. The cost of the fifth operation is $27$. #### Constraints **This problem uses bundled testdata.** - Subtask 1 (1 pts): $N, Q \le 200$. - Subtask 2 (6 pts): All $T_j$ are equal. - Subtask 3 (7 pts): $L_j=R_j$. - Subtask 4 (6 pts): $S_i \le 2$. - Subtask 5 (80 pts): No special restrictions. For $100\%$ of the testdata: - $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$. #### Notes Translated from [The 19th Japanese Olympiad in Informatics, Final Round](https://www.ioi-jp.org/joi/2019/2020-ho/index.html) [E Fire](https://www.ioi-jp.org/joi/2019/2020-ho/2020-ho-t5.pdf)。 Translated by ChatGPT 5