P14370 [JOISC 2018] 最差的记者 3 / Worst Reporter 3

在 IOI 2018 的开幕式上，$N$ 名参赛者排成一列，该列由一条数轴表示。所有参赛者面向数轴的正方向前进。在时间 $0$ 时，第 $i$ 名参赛者（$1 \le i \le N$，从前向后计数）站在坐标 $-i$ 处。此外，旗手 IOI-chan 站在坐标 $0$ 处。 每名参赛者都有一个称为 **迟滞值** 的参数。第 $i$ 名参赛者的 **迟滞值** 为 $D_i$。参赛者遵循以下规则： - 如果第 $i$ 名参赛者与他或她正前方的人（参赛者或 IOI-chan）之间的距离大于或等于 $D_i + 1$，则第 $i$ 名参赛者会移动到距离该人 $1$ 的位置。否则，第 $i$ 名参赛者不移动。 IOI-chan 每单位时间沿数轴正方向移动距离 $1$。每当上述条件满足时，参赛者会立即移动。 你作为记者负责报道开幕式。你本应拍照，但整场仪式期间你都睡着了。没办法——你决定作弊，先拍摄大厅的照片，再在照片上画出人物。 为了避免被发现作弊，或为了估算画图所需的时间，你希望知道以下 $Q$ 个值： - 在时间 $T_j$（$1 \le j \le Q$）时，站在坐标区间 $[L_j, R_j]$（含端点）内的人数。 **任务** 给定每名参赛者的 **迟滞值** 以及 $Q$ 个问题的数据，编写一个程序，计算每个问题所满足条件的人数。

从标准输入读取以下数据： - 输入的第一行包含两个由空格分隔的整数 $N$ 和 $Q$。这表示共有 $N$ 名参赛者（不包括 IOI-chan），以及共有 $Q$ 个问题。 - 接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）包含一个整数 $D_i$。这表示从队首数起的第 $i$ 名参赛者的 **迟滞值** 为 $D_i$。 - 再接下来的 $Q$ 行中，第 $j$ 行（$1 \le j \le Q$）包含三个由空格分隔的整数 $T_j$、$L_j$ 和 $R_j$。这些值代表第 $j$ 个问题。

向标准输出写入 $Q$ 行。第 $j$ 行（$1 \le j \le Q$）应包含第 $j$ 个问题的答案。

### 样例 1 解释 在本示例输入中，参赛者与 IOI-chan 的移动过程如下。 以下内容中，区间 $[L, R]$ 表示数轴上坐标介于 $L$ 与 $R$ 之间（含端点）的所有点的集合。 - 在时间 $0$，IOI-chan 站在坐标 $0$ 处。第 1、2、3 名参赛者分别站在坐标 $-1$、$-2$ 和 $-3$ 处。 - 在时间 $1$，IOI-chan 移动到坐标 $1$。无参赛者移动；第 1、2、3 名参赛者仍分别站在坐标 $-1$、$-2$ 和 $-3$ 处。由于区间 $[2, 4]$ 内无人，第一个问题的输出为 $0$。 - 在时间 $2$，IOI-chan 移动到坐标 $2$。此时 IOI-chan 与第 1 名参赛者之间的距离为 $3$，因此第 1 名参赛者移动到坐标 $1$。第 1、2、3 名参赛者分别站在坐标 $1$、$-2$ 和 $-3$ 处。由于区间 $[2, 4]$ 内仅有 IOI-chan，第二个问题的输出为 $1$。 - 在时间 $3$，IOI-chan 移动到坐标 $3$。无参赛者移动；第 1、2、3 名参赛者仍分别站在坐标 $1$、$-2$ 和 $-3$ 处。由于区间 $[2, 4]$ 内仅有 IOI-chan，第三个问题的输出为 $1$。 - 在时间 $4$，IOI-chan 移动到坐标 $4$。此时 IOI-chan 与第 1 名参赛者之间的距离为 $3$，因此第 1 名参赛者移动到坐标 $3$。第 1、2、3 名参赛者分别站在坐标 $3$、$-2$ 和 $-3$ 处。由于区间 $[2, 4]$ 内有 IOI-chan 和第 1 名参赛者，第四个问题的输出为 $2$。 - 在时间 $5$，IOI-chan 移动到坐标 $5$。无参赛者移动；第 1、2、3 名参赛者仍分别站在坐标 $3$、$-2$ 和 $-3$ 处。由于区间 $[2, 4]$ 内仅有第 1 名参赛者，第五个问题的输出为 $1$。 - 在时间 $6$，IOI-chan 移动到坐标 $6$。此时 IOI-chan 与第 1 名参赛者之间的距离为 $3$，因此第 1 名参赛者移动到坐标 $5$。接着，第 1 名与第 2 名参赛者之间的距离变为 $7$，因此第 2 名参赛者移动到坐标 $4$。此外，第 2 名与第 3 名参赛者之间的距离也变为 $7$，因此第 3 名参赛者移动到坐标 $3$。第 1、2、3 名参赛者分别站在坐标 $5$、$4$ 和 $3$ 处。由于区间 $[2, 4]$ 内有第 2 名和第 3 名参赛者，第六个问题的输出为 $2$。 ### 数据范围 所有输入数据满足以下条件： - $1 \le N \le 500\,000$。 - $1 \le Q \le 500\,000$。 - $1 \le D_i \le 1\,000\,000\,000$（$1 \le i \le N$）。 - $1 \le T_j \le 1\,000\,000\,000$（$1 \le j \le Q$）。 - $1 \le L_j \le R_j \le 1\,000\,000\,000$（$1 \le j \le Q$）。 ### 子任务 共有 3 个子任务。每个子任务的得分及附加约束如下： **子任务 1 [7 分]** - $D_i = 1$（$1 \le i \le N$）。 **子任务 2 [12 分]** - $N \le 1\,000$。 - $Q \le 1\,000$。 - $T_j \le 1\,000$（$1 \le j \le Q$）。 - $1 \le L_j \le R_j \le 1\,000$（$1 \le j \le Q$）。 **子任务 3 [81 分]** 无附加约束。 翻译由 Qwen3-235B 完成