题解：P11232 [CSP-S 2024] 超速检测（民间数据）
XoCeLHsL
·
·
题解
挺麻烦的一个题，赛时调了 2h 。
先写暴力
### 考虑优化掉 $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)
- 如果 $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})$ 。
代码略（