题解

思路

区间模型

第 $i$ 只鸭子能够被击中的时刻组成闭区间

若 $t_i<0$，这只鸭子在允许射击之前已经飞过原点，必定无法击中。于是问题变为：在非负时间轴上选若干点，相邻两点距离至少为 $r$，使被这些点刺中的区间数最多。

所有端点和 $r$ 都是整数。固定一组被刺中的区间后，可行射击时刻只受整数端点约束和形如 $x_{j+1}-x_j\ge r$ 的差分约束；若可行，就存在整数顶点解。因此只需考虑整数时刻。

做法

子任务 1：枚举射击集合

时间坐标不超过 $18$。枚举时刻 $0,1,\ldots,18$ 的全部子集，检查相邻射击是否满足间隔限制，再逐个区间统计是否被刺中。复杂度为 $O(nT2^T)$，其中 $T\le19$。

子任务 2：稠密坐标动态规划

从小到大枚举每个整数时刻 $x$。令 $dp_s$ 表示已经处理完右端点小于 $x$ 的区间、最后一次射击位于 $s$ 时的最少漏掉数量，另设“从未射击”状态。

在 $x$ 射击时，前一次射击必须满足 $s\le x-r$，所以新状态的初值是这些状态的最小值。随后处理所有右端点等于 $x$ 的区间 $[l,x]$：最后射击位置小于 $l$ 的状态会漏掉它，代价加一；位置至少为 $l$ 的状态已经击中它。

直接维护所有坐标即可通过第二个子任务。复杂度为 $O(nT+T^2)$，这里 $T\le2000$。

子任务 3：$r=1$

每个可击中的区间都含有整数时刻，且不同整数时刻之间的距离至少为 $1$。在每个整数时刻都射击即可击中所有满足 $t_i\ge0$ 的鸭子。

满分算法：稀疏事件与平衡树

为统一“第一次射击”，把每个可击中区间整体向右平移 $r$，并在位置 $0$ 放置一次虚拟射击。原区间变为

虚拟射击位于所有区间左侧，且任意真实射击位置都至少为 $r$，因此它不会击中鸭子，也不会改变原问题。

定义函数 $F_x(s)$：只考虑 $R_i\le x$ 的区间，并规定最后一次射击位于 $s$ 时，最少漏掉多少个区间。只需保存 $0\le s\le x$；为了跳过很长的空坐标段，把最右侧常值段向正无穷延伸。

从 $x-1$ 转移到 $x$ 有两种操作。

1. 在 $x$ 新射击。其前一次射击位置至多为 $x-r$，故

   $$F_x(x)=\min_{0\le s\le x-r}F_{x-1}(s).$$

2. 对每个在 $x$ 结束的区间 $[L_i,x]$，所有 $s<L_i$ 的状态都没有射中它，故把函数前缀 $[0,L_i)$ 整体加一；其余状态不变。

因此需要维护一个分段常值函数，并支持：

• 前缀加一；
• 查询前缀最小值；
• 查询某点所在常值段的值；
• 找到给定位置之后第一个值低于指定值的断点；
• 在最右端加入新断点。

用带懒标记和子树最小值的平衡树保存“断点位置、该段函数值”。以上操作均为 $O(\log n)$。

不需要逐个扫描最多 $10^9$ 个时刻。设当前最右侧函数值为 $v$，下一时刻对应的前缀右端为 $q=x+1-r$：

• 若 $[0,q]$ 的最小值不等于 $v$，下一时刻立刻产生新断点；
• 否则，只有当 $q$ 移到第一个函数值小于 $v$ 的断点时才会变化，该事件发生在“断点位置 $+r$”；
• 鸭子右端点也是事件，前缀加一后重新计算下一事件。

每只鸭子只产生一次前缀加事件。前缀最小值是非负整数，总增加量不超过 $n$；由断点进入前缀造成的下降总次数也不超过相应增加次数与初始范围，因此非平凡转移事件总数为 $O(n)$。

复杂度

枚举算法的时间复杂度为 $O(nT2^T)$，空间复杂度为 $O(n)$。稠密坐标动态规划的时间复杂度为 $O(nT+T^2)$，空间复杂度为 $O(T)$。满分算法的时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。

正确性证明

区间模型准确刻画了鸭子与 $O_y$ 轴相交的全部允许时刻。虚拟射击既不命中任何平移后的区间，又恰好允许任意非负真实时刻成为第一次射击。

对固定的 $x,s$，若在 $x$ 新射击，所有此前决策只能以某个 $p\le x-r$ 结束，取其最小代价恰得新状态；若不在 $x$ 新射击，则一个右端点为 $x$ 的区间只有在最后射击 $s\ge L_i$ 时才被命中，故恰好对 $s<L_i$ 的状态加一。两类转移覆盖所有合法方案且互不遗漏，所以归纳可知 $F_x(s)$ 等于定义中的最小漏掉数量。

事件跳跃期间既没有区间结束，移动的前缀最小值也未改变，因此被跳过坐标的新状态与当前最右常值段相同，不会产生新断点；算法只跳过无效转移。最终函数全局最小值就是最少漏掉的可击中鸭子数，用可击中数量减去它即为最大命中数量。