← 返回题目列表

AtCoder · abc455_f

I. 合并史莱姆 2

中文机器翻译题面 查看原题

分数: 525 点

问题陈述

有一个序列 A of N 非负整数,全部初始 0。 工艺流程 Q 按顺序给出查询。
对于 q-th 查询,您得到整数 l_q, r_q 满意 1 \leq l_q \leq r_q \leq N 和一个正整数 a_q。按顺序执行以下操作:

  • 添加 a_q 到每个 A_{l_q}, A_{{l_q}+1}, \dots, A_{r_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 史莱姆 1,2,\dots,M,其中 m-th 史莱姆有重量 B_m.
重复选择两个史莱姆并将它们合并的操作 M-1 次。
当重物变成粘液时 x 和 y 合并,重量粘液 x+y 出现,原来的两个史莱姆消失。这会产生以下费用 x \times y.
查找,取模 998244353,最小可能的总成本 M-1 操作。

请注意,所做的更改 每个查询中的 A 会延续到后续查询。

约束

  • 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
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

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

5 4
1 3 22
3 4 13
5 5 455
1 5 1000000000

示例输出 1

1452
455
0
21421644

第一次查询后, 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.