题意理解

小 F 从 $(0,0)$ 出发，要接住 $n$ 个在 $(t_i,x_i)$ 位置下落的球。规则如下：

• 小 F 每单位时间可以移动 $-1,0,+1$ 的距离
• 可以在任意位置放置分身，但放置新分身时旧分身立即消失
• 在 $t_i$ 时刻，小 F 或分身必须恰好在 $x_i$ 位置

问是否存在方案接住所有球。

核心思路

关键观察 1：时间单调性

由于 $t_i$ 单调不减，我们可以按时间顺序处理事件。

关键观察 2：可达性条件

从 $(t_a,x_a)$ 到 $(t_b,x_b)$ 的可达条件为：

$$|x_b - x_a| \leq t_b - t_a$$

即曼哈顿距离不超过时间差。

关键观察 3：分身策略的本质

放置分身的本质是：在某个时刻，让小 F 的"责任范围"分裂成多个独立的区间。

设 $dp[i]$ 表示处理完前 $i$ 个球后，小 F 本体可能的位置集合（通常是一个区间）。

算法框架

方法一：区间动态规划

定义状态：

• $L[i]$：处理完前 $i$ 个球后，小 F 本体可能的最小位置
• $R[i]$：处理完前 $i$ 个球后，小 F 本体可能的最大位置

转移时考虑两种策略：

策略 A：小 F 亲自接第 $i$ 个球 需要满足：从 $[L[i-1], R[i-1]]$ 中的某个位置，在 $\Delta t = t_i - t_{i-1}$ 时间内能到达 $x_i$

策略 B：用分身接第 $i$ 个球 需要满足：存在某个时刻 $t_j$ ($j < i$)，小 F 在 $x_i$ 位置放置了分身

方法二：贪心维护可达区间

维护区间 $[L,R]$ 表示小 F 当前可能的位置范围。

对于每个新球 $(t_i,x_i)$：

1. 先扩展区间：由于时间流逝，区间扩展为：

   $$[L - \Delta t, R + \Delta t]$$

   其中 $\Delta t = t_i - t_{i-1}$

2. 检查可达性：如果 $x_i$ 在扩展后的区间内，说明小 F 可以亲自接球 此时区间收缩为单个点 $\{x_i\}$

3. 如果不可达：考虑用分身接球 需要检查之前是否存在某个时刻，小 F 经过 $x_i$ 并放置了分身

方法三：分身时间窗口分析

对于用分身接球的情况，关键是要在球下落之前经过该位置。

设 $last[x]$ 表示小 F 最后一次经过位置 $x$ 的时间。

对于球 $(t_i,x_i)$，如果用分身接，需要满足：

• 存在 $j < i$，使得小 F 在时刻 $t_j$ 经过 $x_i$
• 从 $t_j$ 到 $t_i$ 期间，没有放置其他分身（因为新分身会使旧分身消失）

具体实现分析

状态设计优化

由于 $|x_i| \leq 10^9$，不能直接记录所有位置。 但注意到小 F 的位置范围始终是一个区间，可以用 $O(1)$ 的状态表示。

分身管理策略

维护一个集合 $S$ 表示当前有效的分身位置。 当放置新分身时，清空 $S$ 并加入新位置。

对于球 $(t_i,x_i)$：

• 如果 $x_i \in S$，可以用分身接
• 否则，如果小 F 能到达 $x_i$，可以放置分身接这个球

时间复杂度优化

直接实现是 $O(n^2)$ 的，需要优化到 $O(n)$ 或 $O(n \log n)$。

优化技巧：

• 用双指针维护有效的分身位置
• 利用时间单调性剪枝
• 使用并查集或线段树维护位置关系

特殊情况处理

特殊性质：$x_i$ 互不相同

这简化了分身管理，因为每个位置最多对应一个球。

边界情况

• $n=0$：直接输出 YES
• 第一个球：检查从 $(0,0)$ 是否可达
• 时间差为 0：多个球同时下落，需要特殊处理

复杂度分析

最优复杂度：$O(n)$

• 按时间顺序扫描每个球
• 维护常数个状态变量
• 使用合适的数据结构管理分身

总结

本题的核心在于：

1. 问题转化：将接球问题转化为区间可达性问题
2. 状态设计：用区间表示小 F 的可能位置范围
3. 策略分析：区分本体接球和分身接球两种情况
4. 算法优化：利用单调性和区间性质降低复杂度

这是一个典型的动态规划 + 贪心问题，考察选手对状态设计和策略分析的能力。