题意简化

$n$ 个选手（$n \le 50$），每个选手 $i$ 的得分在 $[l_i, r_i]$ 上均匀分布。
问：对于每个名次 $j$（第1名最高），哪个选手最可能获得这个名次？

核心思想：离散化 + 动态规划

1. 概率模型

选手 $i$ 得分为 $x_i \sim U[l_i, r_i]$，相互独立。
我们需要计算每个选手获得每个名次的概率。

由于是连续分布，直接计算积分困难。代码采用离散化方法。

2. 离散化得分区间

将所有 $l_i$ 和 $r_i$ 排序，得到分割点数组 $b[]$。
每个小区间 $[b_{pos}, b_{pos+1}]$ 内，选手得分概率分布可以近似处理。

对于选手 $i$，考虑其得分落在区间 $[b_{pos}, b_{pos+1}]$ 的情况。

3. DP 状态定义

对于固定的选手 $i$ 和区间 $[b_{pos}, b_{pos+1}]$，定义：

其中：

• $rk$：有多少个选手严格高于选手 $i$ 的当前得分
• $len$：有多少个选手与选手 $i$ 同分（在同一小区间内）

4. DP 转移

依次考虑其他选手 $j$（$j \neq i$）： 设选手 $j$ 的得分：

• 比 $[b_{pos}, b_{pos+1}]$ 高：概率 $pre = \frac{b_{pos} - L_j}{R_j-L_j}$（如果 $R_j \le b_{pos}$ 则 $pre=1$）
• 落在 $[b_{pos}, b_{pos+1}]$：概率 $mid = \frac{b_{pos+1}-b_{pos}}{R_j-L_j}$
• 比 $[b_{pos}, b_{pos+1}]$ 低：概率 $suc = 1-pre-mid$

转移：

• 如果 $j$ 得分更高：$dp[rk+1][len] += pre \times dp[rk][len]$
• 如果 $j$ 同分：$dp[rk][len+1] += mid \times dp[rk][len]$
• 如果 $j$ 得分更低：$dp[rk][len] = suc \times dp[rk][len]$

5. 计算名次概率

选手 $i$ 的名次取决于：

• 有 $rk$ 个选手比他高
• 有 $len-1$ 个选手与他同分（包括自己）

他的名次可能是 $rk+1, rk+2, \dots, rk+len$ 中的任意一个（同分随机排名）。

假设同分时名次均匀分布，那么选手 $i$ 获得名次 $j$（$j \in [rk+1, rk+len]$）的概率为：

其中 $d = \frac{b_{pos+1}-b_{pos}}{R_i-L_i}$ 是选手 $i$ 得分落在该区间的概率。

累加所有区间得到 $ans[i][j]$：选手 $i$ 获得第 $j$ 名的概率。

6. 输出答案

对于每个名次 $j$，找 $ans[i][j]$ 最大的选手 $i$，输出编号。

算法步骤

1. 离散化：收集所有 $l_i$ 和 $r_i$，排序去重
2. 枚举选手 $i$：作为当前考察对象
3. 枚举区间 $[b_{pos}, b_{pos+1}]$：选手 $i$ 可能得分的区间
4. DP 计算：计算其他选手相对于该区间的排名分布
5. 更新概率：根据 DP 结果更新 $ans[i][j]$
6. 输出结果：对每个名次选择概率最大的选手

复杂度分析

• 离散化：$O(n)$，$b$ 数组大小 $O(n)$
• 三重循环：
  • 选手 $i$：$n$
  • 区间 $pos$：$O(n)$
  • 其他选手 $j$：$n$
  • DP 转移：$O(n^2)$
• 总复杂度：$O(n^4)$，$n=50$ 时 $50^4=6.25\times 10^6$，可过

关键点

1. 离散化近似：将连续分布转化为小区间上的均匀分布
2. DP 状态设计：$(rk, len)$ 分别表示严格更高和同分的选手数
3. 同分处理：假设同分时名次均匀随机
4. 概率累加：对每个选手每个可能得分区间分别计算

样例解释

样例1：选手1区间[1,6]，选手2区间[4,9]

• 第1名：选手1更可能（有较低分数段优势）
• 第2名：选手2更可能

样例2：8个选手区间依次错开
每个选手在自己的区间有优势，所以名次与编号一致。

代码特点

• 使用 eqs=1e-11 作为浮点数精度判断
• DP 数组重用，每轮清零
• 注意边界条件处理（$R_j \le b_{pos}$ 等）
• 输出时误差 $10^{-6}$ 内取编号小的