/ 
実行時間制限: 3 sec / メモリ制限: 1024 MiB
配点 : 525 点
問題文
長さ N の非負整数列 A があり、最初はすべての要素が 0 です。
Q 個のクエリが与えられるので順に処理してください。
q 番目のクエリでは 1 \leq l_q \leq r_q \leq N を満たす整数 l_q,r_q と正整数 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 個のスライム 1,2,\dots,M があって、m 個目のスライムの重さは B_m です。
2 個のスライムを選び、合成させるという操作を M-1 回繰り返します。
重さが x,y のスライムを合成させると重さ x+y のスライムが出現し、元の 2 個のスライムは消えます。このとき x \times y のコストがかかります。
M-1 回の操作のコストの総和としてあり得る値の最小値を 998244353 で割った余りを求めてください。
各クエリでの 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
1 番目のクエリの後、A=(22,22,22,0,0) となり、B=(22,22,22) です。1 回目に 1 つ目のスライムと 3 つ目のスライムを合成すると、そのコストは 22 \times 22=484 です。次に残った 2 つのスライムを合成するとそのコストは 22 \times 44=968 です。このときコストの合計は 484+968=1452 です。また、コストの合計をこれよりも小さくすることはできません。
2 番目のクエリの後、A=(22,22,35,13,0) となり、B=(35,13) です。求める答えは 35 \times 13 = 455 です。
Score : 525 points
Problem Statement
There is a sequence A of N non-negative integers, all initially 0.
Process Q queries given in order.
For the q-th query, you are given integers l_q, r_q satisfying 1 \leq l_q \leq r_q \leq N and a positive integer a_q. Perform the following in order:
- Add a_q to each of A_{l_q}, A_{{l_q}+1}, \dots, A_{r_q}.
- Then, letting M=r_q-l_q+1 and B=(B_1,B_2,\dots,B_M)=(A_{l_q}, A_{l_q+1}, \dots, A_{r_q}), find the answer to the following problem:
There are M slimes 1,2,\dots,M, where the m-th slime has weight B_m.
Repeat the operation of choosing two slimes and merging them M-1 times.
When slimes of weights x and y are merged, a slime of weight x+y appears and the original two slimes disappear. This incurs a cost of x \times y.
Find, modulo 998244353, the minimum possible total cost of the M-1 operations.
Note that the changes made on A in each query carry over to subsequent queries.
Constraints
- 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
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N Q l_1 r_1 a_1 l_2 r_2 a_2 \vdots l_Q r_Q a_Q
Output
Output the answers over Q lines in total. The q-th line should contain the answer to the q-th query.
Sample Input 1
5 4 1 3 22 3 4 13 5 5 455 1 5 1000000000
Sample Output 1
1452 455 0 21421644
After the first query, A=(22,22,22,0,0) and B=(22,22,22). Merging the first and third slimes first incurs a cost of 22 \times 22=484. Then merging the remaining two slimes incurs a cost of 22 \times 44=968. The total cost is 484+968=1452. Moreover, the total cost cannot be made smaller than this.
After the second query, A=(22,22,35,13,0) and B=(35,13). The answer is 35 \times 13 = 455.