AT_abc255_h [ABC255Ex] Range Harvest Query

题目描述

有 $N$ 棵树。第 $0$ 天时，每棵树上都没有果实。
从第 $1$ 天早晨开始，对于每一天的早晨，对于每一棵 $i=1,2,\ldots,N$ 的树，第 $i$ 棵树会多长出 $i$ 个果实。

高桥君会进行 $Q$ 次收获操作。对于每一次 $i=1,2,\ldots,Q$，第 $i$ 次收获操作会在第 $D_i$ 天的晚上进行，此时他会收获第 $L_i$ 棵到第 $R_i$ 棵树上的所有果实。

请对于每一次收获操作，输出高桥君收获的果实数量对 $998244353$ 取模的结果。

输入格式

输入以如下格式从标准输入给出。

$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

输入 #1

5 3
2 2 3
3 3 4
5 1 5

输出 #1

10
15
50

输入输出样例 #2

输入 #2

711741968710511029 1
82803157126515475 516874290286751784 588060532191410838

输出 #2

603657470

说明/提示

限制条件

• $1 \leq N \leq 10^{18}$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq D_1 < D_2 < \cdots < D_Q \leq 10^{18}$
• $1 \leq L_i \leq R_i \leq N$
• 输入均为整数

样例解释 1

对于 $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

请注意要对 $998244353$ 取模输出。

由 ChatGPT 4.1 翻译