AT_abc455_f [ABC455F] Merge Slimes 2

有一个长度为 $N$ 的非负整数序列 $A$，初始时所有元素均为 $0$。现有 $Q$ 个操作，按照顺序依次处理。 对于第 $q$ 个操作，给定整数 $l_q, r_q$，满足 $1 \leq l_q \leq r_q \leq N$，以及一个正整数 $a_q$。请按如下步骤依次进行： - 对 $A_{l_q}, A_{l_q+1}, \dots, A_{r_q}$ 中的每个元素都加上 $a_q$。 - 然后，令 $M = r_q - l_q + 1$，设 $B = (B_1, B_2, \dots, B_M) = (A_{l_q}, A_{l_q+1}, \dots, A_{r_q})$，请解答以下问题： > 有 $M$ 个史莱姆，第 $m$ 个史莱姆的重量为 $B_m$。 > 一共进行 $M-1$ 次操作，每次操作选择两个史莱姆合并。 > 当合并重量为 $x$ 和 $y$ 的两个史莱姆时，会出现一个重量为 $x+y$ 的新史莱姆，原来的两个史莱姆消失，花费为 $x \times y$。 > 请计算这 $M-1$ 次合并的最小可能总代价，并对 $998244353$ 取模。 注意，序列 $A$ 在每次操作中的变化会影响后续操作。

输入从标准输入读入，格式如下： > $N$ $Q$ > $l_1$ $r_1$ $a_1$ > $l_2$ $r_2$ $a_2$ > $\vdots$ > $l_Q$ $r_Q$ $a_Q$

共输出 $Q$ 行，第 $q$ 行输出第 $q$ 个操作的答案。

### 样例解释 1 第一次操作后，$A = (22, 22, 22, 0, 0)$，$B = (22, 22, 22)$。如果先合并第一个和第三个史莱姆，花费 $22 \times 22 = 484$，再合并剩下的两个，花费 $22 \times 44 = 968$，总代价为 $484 + 968 = 1452$，且无法得到更小的总花费。 第二次操作后，$A = (22, 22, 35, 13, 0)$，$B = (35, 13)$，答案为 $35 \times 13 = 455$。 ### 数据范围 - $1 \leq N \leq 10^5$ - $1 \leq Q \leq 10^5$ - $1 \leq l_q \leq r_q \leq N$ - $1 \leq a_q \leq 10^9$ - 所有输入均为整数。 由 ChatGPT 5 翻译