AT_otemae2019_e 最悪の教頭 (Worst Head Teacher)

在大手前编程竞赛21XX的开幕式上，$N$ 名学生排成一列进行行进。行进路径可视为数轴，所有学生面向数轴正方向行走。在时刻 $0$ 时，第 $i$ 个学生（$1 \leq i \leq N$）的位置为坐标 $-i$。坐标 $0$ 上站着举旗的校长皮太郎。 每个单位时间内，皮太郎校长沿数轴正方向前进一单位距离。 每个学生有一个特定的“悠然度”值，表示他们前进的条件。第 $i$ 个学生的悠然度为 $D_i$。在每个单位时间内，学生们会根据以下规则行动： - 在时刻 $0$，如果第 $i$ 个学生与他前方参与者（包括学生或校长）的距离正好为 $D_i$，该学生向前移动一个单位；否则停留在原地。 你是该活动的副校长兼教头来的木姆。由于开幕式期间你不小心睡着了，而错过拍照打卡的机会，只好拍摄场地的照片后，通过在照片上绘制图像来填补缺憾。 为了不被发现照片是伪造的，并评估绘制任务的工作量，你需要知道以下 $Q$ 个时刻的信息： - 在时刻 $T_j$ 时，位于坐标 $L_j$ 到 $R_j$ （包括两端）之间的参与者人数是多少（$1 \leq j \leq Q$）。 请根据每位学生的悠然度和给定的 $Q$ 个查询，编写程序，计算每个查询中符合条件的参与者数量。

通过标准输入读取数据，输入格式如下： > $N$ $Q$ $D_1$ $\ldots$ $D_N$ $T_1$ $L_1$ $R_1$ $\ldots$ $T_Q$ $L_Q$ $R_Q$

输出符合条件的参与者数量，逐行输出 $Q$ 行。第 $j$ 行（$1 \leq j \leq Q$）输出第 $j$ 个查询的答案。

- 所有输入均为整数。 - $1 \leq N \leq 500,000$。 - $1 \leq Q \leq 500,000$。 - $1 \leq D_i \leq 1,000,000,000$（$1 \leq i \leq N$）。 - $1 \leq T_j \leq 1,000,000,000$（$1 \leq j \leq Q$）。 - $1 \leq L_j \leq R_j \leq 1,000,000,000$（$1 \leq j \leq Q$）。 ### 子任务 1. （15 分）$N, Q, D_i, T_j, L_j, R_j \leq 1,000$（$1 \leq i \leq N, 1 \leq j \leq Q$）。 2. （16 分）$T_i = T_j$（$1 \leq i, j \leq Q$）。 3. （69 分）无其他特定约束。 ### 示例解释 在时刻 $0$，校长和选手 $1$、$2$、$3$ 分别位于坐标 $0, -1, -2, -3$。在时刻 $1$，他们分别在坐标 $1, -1, -2, -3$ 处。在时刻 $2$，则分别在坐标 $2, 0, -2, -3$，因为： - 校长移动到了位置 $2$。 - 选手 $1$ 与他前面参与者的距离变成了 $2$，所以前进到位置 $0$。 - 选手 $2$ 与前面指引者的距离未达到 $5$，故未移动。 - 选手 $3$ 与前面指引者的距离未达 $3$，故未移动。 时刻 $3$ 时，他们分别位于坐标 $3, 1, -2, -3$。 **本翻译由 AI 自动生成**