P11037 题解
wangshi
·
·
题解
先化简一下方差的式子。
\begin{aligned}
\mu&=\frac{1}{n}\sum\limits_{i=1}^{n} a_i \\
s^2&=\frac{1}{n}\sum\limits_{i=1}^{n} (a_i-\mu)^2 \\
s^2&=\frac{1}{n}\sum\limits_{i=1}^{n} (a_i-2a_i\mu+\mu^2) \\
s^2&=\frac{1}{n}\sum\limits_{i=1}^{n} (a_i-2a_i\mu+\mu^2) \\
s^2&=\mu^2-\frac{-2\mu}{n} \sum\limits_{i=1}^{n} a_i+\sum\limits_{i=1}^{n}a_i^2 \\
s^2&=-\mu^2+\frac{1}{n}\sum\limits_{i=1}^{n}a_i^2
\end{aligned}
首先询问的最小值为所有区间左端点的和，然后每次选择一个合法的最小值增大一，设最小值增大到的最大值的位置为 pos，显然可以直接二分求出这个位置。
然后考虑每个区间的贡献。
- 对于 r_i < pos 的区间贡献为 r_i。
- 对于 l_i > pos 的区间贡献为 l_i。
- 对于 l_i \leq pos \leq r_i 的区间，有一部分贡献 pos，其余为 pos-1。
这些均可以预处理求出，时间复杂度为 O(n \log n)。
code