问题理解

我们有 $n$ 枚导弹，每枚导弹有高度 $h_i$ 和速度 $v_i$。
拦截规则：系统第一发可以拦截任意导弹，之后拦截的导弹必须满足 高度不高于前一发 且 速度不大于前一发。
目标：在 拦截数量最多 的前提下，计算 每枚导弹被拦截的概率。

---

关键观察

1. 问题转化

这实际上是一个 二维最长不升子序列（2D LIS） 问题：

• 我们需要找一个序列 $p_1, p_2, \dots, p_k$，满足：
  • $h_{p_1} \geq h_{p_2} \geq \dots \geq h_{p_k}$
  • $v_{p_1} \geq v_{p_2} \geq \dots \geq v_{p_k}$

2. 图论视角

将导弹看作节点，如果导弹 $i$ 能在导弹 $j$ 之后被拦截（即 $h_i \leq h_j$ 且 $v_i \leq v_j$），则从 $j$ 向 $i$ 连一条有向边。
这样形成一个 DAG（有向无环图），原问题转化为：

• 求 DAG 上的 最长路径（即最多拦截数量）
• 计算每个节点在 所有最长路径 中出现的概率

---

算法框架

第一步：求最长链长度

定义：

• $dpLen[i]$：以第 $i$ 枚导弹结尾的最长链长度
• $dpCnt[i]$：以第 $i$ 枚导弹结尾的、长度为 $dpLen[i]$ 的链的方案数

转移： 对于每个 $i$，找到所有满足 $h_j \geq h_i$ 且 $v_j \geq v_i$ 的 $j$：

• 如果 $dpLen[j] + 1 > dpLen[i]$，则更新 $dpLen[i]$ 和 $dpCnt[i]$
• 如果 $dpLen[j] + 1 = dpLen[i]$，则累加 $dpCnt[i]$

优化：
由于直接枚举是 $O(n^2)$，需要数据结构优化。对导弹按 $h$ 降序排序（$h$ 相同时按 $v$ 降序），然后用 树状数组/线段树 维护 $(v, dpLen, dpCnt)$ 信息：

• 在树状数组中查询 $v \geq v_i$ 的区域中的最大 $dpLen$ 及对应方案数
• 然后将当前导弹的 $(v_i, dpLen[i], dpCnt[i])$ 插入树状数组

第二步：计算概率

定义：

• $f[i]$：以第 $i$ 枚导弹开头的方案数（反向DP）
• $g[i]$：以第 $i$ 枚导弹结尾的方案数（即 $dpCnt[i]$）

关键公式：
导弹 $i$ 被拦截的概率 =
[ \frac{\sum_{\text{所有最长链经过i}} 1}{\text{最长链总方案数}} = \frac{f[i] \times g[i]}{\text{总方案数}} ] 其中：

• $f[i]$ 可以通过 反向DP 求得（按 $h$ 升序、$v$ 升序排序，用树状数组维护）
• $g[i]$ 就是第一步中求得的 $dpCnt[i]$
• 总方案数 = $\sum_{dpLen[i] = \text{maxLen}} g[i]$

---

实现细节

1. 离散化

由于 $h_i, v_i \leq 10^9$，需要先对 $h$ 和 $v$ 分别离散化，将值域映射到 $[1, n]$。

2. 排序技巧

• 正向DP：按 $h$ 降序，$h$ 相同时按 $v$ 降序（确保能转移到当前导弹的都在前面处理过）
• 反向DP：按 $h$ 升序，$h$ 相同时按 $v$ 升序

3. 数据结构维护

树状数组/线段树需要维护：

• 最大值 $maxLen$
• 对应方案数 $sumCnt$
• 合并时：如果 $len_1 > len_2$，取 $len_1$ 和 $cnt_1$；如果相等，累加 $cnt_1 + cnt_2$

4. 概率计算

对于每枚导弹 $i$：

• 如果 $dpLen[i] + fLen[i] - 1 \neq maxLen$，说明不在任何最长链上，概率为 $0$
• 否则，概率 = $\frac{fCnt[i] \times gCnt[i]}{totalCnt}$

---

样例分析

样例：

4
3 30
4 40  
6 60
3 30

最长链长度为 $2$，最长链有 $3$ 条：

• (2,4)：导弹2→导弹4
• (3,4)：导弹3→导弹4
• (1,4)：导弹1→导弹4

因此：

• 导弹1、2、3分别出现在 $1/3$ 的最长链中
• 导弹4出现在所有最长链中，概率为 $1$

输出：

2
0.33333 0.33333 0.33333 1.00000

---

复杂度分析

• 离散化：$O(n \log n)$
• 两次DP（正向+反向）：$O(n \log n)$
• 总复杂度：$O(n \log n)$，可处理 $n = 5 \times 10^4$

---

总结

这道题的核心是：

1. 二维最长不升子序列 的求解与优化
2. DAG上最长路径计数 的正反两次DP
3. 概率计算 通过方案数相乘除以总方案数
4. 数据结构优化 处理二维偏序关系

通过离散化+树状数组/线段树，将 $O(n^2)$ 优化到 $O(n \log n)$，是处理大规模二维偏序问题的典型方法。