题解

问题分析

题目要求计算Moorhsum在区间$[l, r]$内至少一场获得省选资格的概率。每场比赛中，他的排名在$[1, x]$内随机，第$i$场需排名$\leq a_i$才能获得资格。

核心思路：
至少一场合格的概率 = $1 -$ 所有场都不合格的概率。
因此，问题转化为计算“所有场都不合格”的概率（记为$P$），最终答案为$1-P$。

单场不合格的概率为$\frac{x - a_i}{x} = 1 - \frac{a_i}{x}$。
多场都不合格的概率为各场不合格概率的乘积（因每场独立）：

算法设计

直接计算乘积的挑战在于$n, q$可达$6 \times 10^5$，暴力计算每个询问的乘积会超时。需要优化计算效率：

1. 分治 + ST表加速：
   利用ST表预处理区间最大值，分治时优先处理区间内的最大值$a_{max}$：

   • 若$a_{max} \times 2 > x$，则$\frac{a_{max}}{x}$较大，直接计算该场的乘积项，再递归处理左右子区间。
   • 若$a_{max} \times 2 \leq x$，则所有$a_i/x \leq 0.5$，此时用泰勒展开近似计算乘积。

2. 泰勒展开近似：
   当所有$a_i/x \leq 0.5$时，利用对数性质和泰勒展开：

   $$\ln\left(\prod (1 - \frac{a_i}{x})\right) = \sum \ln(1 - \frac{a_i}{x}) \approx -\sum \left( \frac{a_i}{x} + \frac{a_i^2}{2x^2} + \frac{a_i^3}{3x^3} + \cdots + \frac{a_i^k}{kx^k} \right) $$

   取前$30$项即可保证精度（因$a_i/x \leq 0.5$，高阶项衰减极快）。预处理幂次和数组$sum[i][k] = \sum_{j=1}^i \frac{a_j^k}{k}$，可快速计算区间和。

复杂度分析

• 预处理：ST表构建$O(n \log n)$，幂次和数组$O(n \log x)$（取$30$项）。
• 单次查询：分治过程中每个元素被处理一次，结合ST表查询$O(\log n)$，总复杂度$O(q \log n)$。

代码要点

1. ST表：用于快速查询区间最大值，支持分治时的区间划分。
2. 幂次和数组：预处理$sum[i][k]$，加速泰勒展开的区间和计算。
3. 分治递归：根据区间最大值与$x$的关系，选择精确计算或近似计算，平衡效率与精度。

该算法通过分治策略和数学近似，在保证精度的前提下，高效处理了大规模输入，适合$n, q$达$6 \times 10^5$的场景。