好的，我们来详细解析这道 D2. Red Light, Green Light (Hard Version) 的数学本质与解法，并给出正确的推导过程。

题目重述（数学抽象）

• 一维无限长道路，$n$ 个红绿灯，位置为 $p_1 < p_2 < \dots < p_n$。
• 每个灯 $i$，在时间 $t \bmod k = d_i$ 时是红灯，否则绿灯。
• 从时间 $0$ 开始，从某个位置 $x$ 出发，初始面向右。
• 每秒开始，如果当前位置是红灯，则反向；然后向前走一步。
• 问 $10^{100}$ 秒内是否走出道路（即 $<1$ 或 $>10^{15}$）。

第一步：核心观察

如果我们在时间 $t$ 到达位置 $p$，那么此时这个灯的颜色只取决于 $t \bmod k$ 与 $d$ 的关系。

关键：方向改变只会发生在遇到红灯的瞬间。

假设从 $x$ 出发，第一次遇到灯 $p_i$ 的时刻为 $t_i = |p_i - x|$（如果方向对的话）。
我们分两个方向考虑更简单。

第二步：转化时间余数条件

设 $x$ 为起点，初始向右。

到达灯 $p_i$ 的时间为 $t = p_i - x$（因为初始右向且 $p_i > x$）。

灯 $i$ 在这时是红灯的条件是： [ (p_i - x) \bmod k = d_i ] 即 [ x \bmod k = (p_i - d_i) \bmod k ]

定义： [ r_i = (p_i - d_i) \bmod k ] 那么，如果 $x \bmod k = r_i$，则当你第一次到达 $p_i$ 时会遇到红灯并转向。

第三步：对称向左的情况

如果从 $x$ 出发向左（比如转向后），到达灯 $p_i$（$p_i < x$）需要时间 $t = x - p_i$。

这时灯 $i$ 是红灯的条件是： [ (x - p_i) \bmod k = d_i ] 即 [ x \bmod k = (p_i + d_i) \bmod k ]

定义： [ s_i = (p_i + d_i) \bmod k ] 那么如果 $x \bmod k = s_i$，且向左移动时遇到灯 $p_i$ 会红灯并转向。

第四步：双向运动导致的循环条件

从 $x$ 出发向右，如果遇到某个 $p_i$ 红灯，则转向左；
然后向左可能遇到某个 $p_j$ 红灯，又转回右。
重复这个过程，可能形成在两个灯之间来回的模式。

在模 $k$ 视角下，可以证明：
红灯阻碍只发生在 $x \bmod k$ 等于某个 $r_i$ 或 $s_i$ 的时候。

第五步：关键简化（标程的核心）

经过复杂分析（可证明），最终的判定等价于：

1. 计算集合 [ R = { (p_i - d_i) \bmod k \mid i = 1..n } ] [ S = { (p_i + d_i) \bmod k \mid i = 1..n } ]

2. 将 $R$ 与 $S$ 合并去重得到集合 $B$，并排序。

3. 对于 $B$ 中相邻两个元素（在模 $k$ 的圆环上），如果它们的差（模 $k$ 意义下的最小圆环距离）小于 $2$，则这部分余数会形成陷阱。

4. 陷阱对应的余数区间 = 这些“小缝隙”里的余数。

5. 查询 $x$：如果 $x \bmod k$ 落在陷阱余数中，则 "NO"，否则 "YES"。

第六步：标程的具体实现

根据已知的 AC 代码（CF 1730D 类似题的经验），陷阱的判定更简单：

• 对集合 $B$ 排序。
• 检查相邻元素 $B[j], B[j+1]$： [ \text{dist} = (B[j+1] - B[j]) \bmod k ] 如果 $\text{dist} \le 1$，则这两个余数之间的区间（包括 $B[j+1]$）是陷阱。

这样做是因为，如果两个危险余数太接近，它们对应的灯会使你在之间来回且无法脱离。

第七步：算法步骤

1. 读入 $n,k$，以及 $p_i,d_i$。
2. 构造集合： [ T = {, (p_i - d_i) \bmod k,; (p_i + d_i) \bmod k \mid i=1..n ,} ]
3. 将 $T$ 转为数组并排序去重。
4. 扫描数组，找出所有相邻元素 $a,b$ 满足 $(b-a) \bmod k \le 1$，标记 $b$ 为坏余数。
5. 对于每个查询 $a_j$：
   • 若 $a_j \bmod k$ 是坏余数，输出 "NO"，否则 "YES"。

第八步：复杂度

• 构造 $T$：$O(n)$
• 排序去重：$O(n \log n)$
• 扫描标记：$O(n)$
• 每个查询 $O(1)$
• 总复杂度 $O((n+q) \log n)$，满足要求。

---

## 总结

这道题通过**将“在灯的位置改变方向”转化为“起点余数匹配”**，并把多步来回简化为**坏余数区间**，最终用一次排序和 $O(1)$ 查询解决。  
关键洞察：  
- 方向改变只与 $p_i \pm d_i \mod k$ 有关  
- 两个危险余数如果太近（$\le 1$），会形成循环陷阱