题解：P11232 [CSP-S 2024] 超速检测（民间数据）
26 Oct, 2024 11:06 PM +08:00
挺麻烦的一个题，赛时调了 $2h$ 。
先写暴力
$O(nm)$ 算出来第一个输出，然后 $O(2^mnm)$ 枚举删哪些测速点，可以骗到一点分。
考虑优化掉 $O(nm)$
对 $p$ 从小到大排序，设 $v_{i, q}$ 是第 $i$ 辆车在 $q$ 点的速度 ，则对于第 $i$ 辆车 $A$ ：
-
如果 $a_i<0$， $A$ 超速当且仅当 $v_{i, P}>V$ ，其中 $P$ 是最小的 $p_j$ 满足 $p_j\space{\geq}{\space}d_i$
-
如果 $a_i\space{\geq}\space0$， $A$ 超速当且仅当 $v_{i, p_m}>V$
对于 $a_i<0$ ，显然可以二分，整体时间复杂度 $O(n\log{m})$ 。
考虑优化掉 $O(2^mnm)$
$p$ 是有序的，可以把每辆车的测超速范围看成一个线段 $X$ ，具体来说，对于第 $i$ 辆车：
- 如果 $a_i<0$， $X_i=[P,Q]$ ，其中 $P$ 是最小的 $j$ 满足 $v_{i, p_j}>V$ ， $Q$ 是最大的 $j$ 满足 $v_{i, p_j}>V$ 。
- 如果 $a_i\space{\geq}\space0$， $X_i=[P,m]$ ，其中 $P$ 是最小的 $j$ 满足 $v_{i, p_j}>V$ 。
因为 $v_{i, p_j}$ 在 $p_j\space{\geq}{\space}d_i$ 上具有单调性，所以二分求 $X$，时间复杂度 $O(n\log{m})$ 。
此时问题转化成 P1803 线段覆盖，整体时间复杂度 $O(n\log{m})$ 。
代码略（
本文最初发表于 Luogu，于 2026-04-19 同步至本站。