CF1550F Jumping Around

有一个无限大的池塘，可以用一条数轴来表示。池塘中有 $n$ 块石头，编号从 $1$ 到 $n$。第 $i$ 块石头位于整数坐标 $a_i$ 处。所有石头的坐标互不相同。石头按照坐标递增的顺序编号，即 $a_1 < a_2 < \dots < a_n$。 一只机器人青蛙坐在编号为 $s$ 的石头上。这只青蛙可以编程。它有一个基础跳跃距离参数 $d$。此外，还可以设置跳跃距离的范围。如果将跳跃距离范围设置为某个整数 $k$，那么青蛙可以从某块石头跳到任意距离在 $d-k$ 到 $d+k$（包含端点）之间的石头，方向不限。两块石头之间的距离为它们坐标的绝对差。 你的任务是为青蛙实现一个功能。给定两个整数 $i$ 和 $k$，判断青蛙能否通过一系列跳跃（跳跃距离范围均设置为 $k$，跳跃次数不限，可以为零）从编号为 $s$ 的石头跳到编号为 $i$ 的石头。 你将会得到 $q$ 个这样的询问，第 $j$ 个询问包含两个整数 $i$ 和 $k$。如果青蛙能够到达第 $i$ 块石头，输出 "Yes"，否则输出 "No"。 你可以用任意大小写输出 "YES" 和 "NO"（例如 "yEs"、"yes"、"Yes" 和 "YES" 都会被识别为正答案）。

第一行包含四个整数 $n$、$q$、$s$ 和 $d$（$1 \le n, q \le 2 \cdot 10^5$；$1 \le s \le n$；$1 \le d \le 10^6$）——石头的数量、询问的数量、起始石头编号和基础跳跃距离参数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^6$）——每块石头的坐标。所有石头的坐标互不相同。石头按照距离陆地的递增顺序编号，即 $a_1 < a_2 < \dots < a_n$。 接下来的 $q$ 行，每行包含两个整数 $i$ 和 $k$（$1 \le i \le n$；$1 \le k \le 10^6$）——每个询问的参数。

对于每个询问，输出一行答案。如果存在一系列跳跃（跳跃距离范围均为 $k$）可以从编号为 $s$ 的石头跳到编号为 $i$ 的石头，输出 "Yes"；否则输出 "No"。

第一个样例的解释： 在第一个询问中，目标石头和起始石头相同，因此无需跳跃即可到达。 在第二个询问中，青蛙可以跳跃的距离范围为 $[5-2, 5+2]$。因此，它可以向右跳 $7$ 到达第 $5$ 块石头，也可以向左跳 $3$ 到达第 $3$ 块石头。从第 $3$ 块石头可以向左跳 $5$ 到达第 $2$ 块石头，再向左跳 $4$ 到达第 $1$ 块石头。然而，没有办法到达第 $7$ 块石头。 在第三个询问中，青蛙可以跳跃的距离范围为 $[5-3, 5+3]$。因此，它可以先跳到第 $5$ 块石头，再跳到第 $7$ 块石头。 第四个询问的解释见第二个询问的说明。 由 ChatGPT 4.1 翻译