/ 
Time Limit: 8 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 本の木があります。0 日目にはどの木にも実は一つもなっていません。
1 日目以降の毎朝、それぞれの i = 1, 2, \ldots, N について、i 番目の木に i 個の実が増えます。
高橋君は Q 回の収穫作業をします。 i = 1, 2, \ldots, Q について、i 回目の収穫作業は D_i 日目の夜に行われ、その時点で L_i 番目から R_i 番目の木になっているすべての実を収穫します。
Q 回の収穫作業のそれぞれについて、高橋君が収穫する実の個数を 998244353 で割ったあまりを出力してください。
制約
- 1 \leq N \leq 10^{18}
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq D_1 \lt D_2 \lt \cdots \lt D_Q \leq 10^{18}
- 1 \leq L_i \leq R_i \leq N
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N Q D_1 L_1 R_1 D_2 L_2 R_2 \vdots D_Q L_Q R_Q
出力
Q 行出力せよ。 i = 1, 2, \ldots, Q について、i 行目には高橋君が i 回目の収穫作業で収穫する実の個数を 998244353 で割ったあまりを出力せよ。
入力例 1
5 3 2 2 3 3 3 4 5 1 5
出力例 1
10 15 50
i = 1, 2, 3, 4, 5 について、i 番目の木になっている実の個数を A_i とし、 それぞれの木になっている実の個数を数列 A = (A_1, A_2, A_3, A_4, A_5) を用いて表すことにします。
- 0 日目、A = (0, 0, 0, 0, 0) です。
- 1 日目の朝、それぞれの木に新たに実がなり、A = (1, 2, 3, 4, 5) となります。
- 2 日目の朝、それぞれの木に新たに実がなり、A = (2, 4, 6, 8, 10) となります。
- 2 日目の夜、高橋君は 1 回目の収穫を行います。4 + 6 = 10 個の木の実を収穫し、A = (2, 0, 0, 8, 10) となります。
- 3 日目の朝、それぞれの木に新たに実がなり、A = (3, 2, 3, 12, 15) となります。
- 3 日目の夜、高橋君は 2 回目の収穫を行います。3 + 12 = 15 個の木の実を収穫し、A = (3, 2, 0, 0, 15) となります。
- 4 日目の朝、それぞれの木に新たに実がなり、A = (4, 4, 3, 4, 20) となります。
- 5 日目の朝、それぞれの木に新たに実がなり、A = (5, 6, 6, 8, 25) となります。
- 5 日目の夜、高橋君は 3 回目の収穫を行います。5 + 6 + 6 + 8 + 25 = 50 個の木の実を収穫し、A = (0, 0, 0, 0, 0) となります。
入力例 2
711741968710511029 1 82803157126515475 516874290286751784 588060532191410838
出力例 2
603657470
998244353 で割ったあまりを出力することに注意してください。
Score : 600 points
Problem Statement
There are N trees. On Day 0, each tree bears no fruits.
On the morning of Day 1 and subsequent days, the i-th tree bears i new fruits for each i = 1, 2, \ldots, N.
Takahashi will perform Q harvesting. For each i = 1, 2, \ldots, Q, the i-th harvesting takes place on the night of Day D_i, collecting all fruits remaining on the L_i-th through R_i-th trees at that point.
For each of the Q harvesting, print the number of fruits Takahashi will collect, modulo 998244353.
Constraints
- 1 \leq N \leq 10^{18}
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq D_1 \lt D_2 \lt \cdots \lt D_Q \leq 10^{18}
- 1 \leq L_i \leq R_i \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N Q D_1 L_1 R_1 D_2 L_2 R_2 \vdots D_Q L_Q R_Q
Output
Print Q lines. For each i = 1, 2, \ldots, Q, the i-th line should contain the number of fruits Takahashi will collect in the i-th harvesting, modulo 998244353.
Sample Input 1
5 3 2 2 3 3 3 4 5 1 5
Sample Output 1
10 15 50
For each i = 1, 2, 3, 4, 5, let A_i be the number of fruits remaining on the i-th tree. Now, we use the sequence A = (A_1, A_2, A_3, A_4, A_5) to represent the numbers of fruits remaining in the trees.
- On Day 0, we have A = (0, 0, 0, 0, 0).
- On the morning of Day 1, each tree bears new fruits, and we have A = (1, 2, 3, 4, 5).
- On the morning of Day 2, each tree bears new fruits, and we have A = (2, 4, 6, 8, 10).
- On the night of Day 2, Takahashi performs the 1-st harvesting. 4 + 6 = 10 fruits are collected, and we have A = (2, 0, 0, 8, 10).
- On the morning of Day 3, each tree bears new fruits, and we have A = (3, 2, 3, 12, 15).
- On the night of Day 3, Takahashi performs the 2-nd harvesting. 3 + 12 = 15 fruits are collected, and we have A = (3, 2, 0, 0, 15).
- On the morning of Day 4, each tree bears new fruits, and we have A = (4, 4, 3, 4, 20).
- On the morning of Day 5, each tree bears new fruits, and we have A = (5, 6, 6, 8, 25).
- On the night of Day 5, Takahashi performs the 3-rd harvesting. 5 + 6 + 6 + 8 + 25 = 50 fruits are collected, and we have A = (0, 0, 0, 0, 0).
Sample Input 2
711741968710511029 1 82803157126515475 516874290286751784 588060532191410838
Sample Output 2
603657470
Be sure to print the numbers modulo 998244353.