题解：AT_arc111_f [ARC111F] Do you like query problems?

· · 题解

不理解为什么大家的做法这么复杂。

考虑对 a_i 在第 j 次操作的贡献求和，记 p_i=\dfrac{i(n-i+1)}{n(n+1)/2} 为位置 i 在一次操作中被选中的概率，不妨将一个元素被 \max 操作选中的一次视为是赋值操作，则由对称性知其期望恒为 \dfrac{m-1}{2}，故答案为：

\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{q}\dfrac{1}{2m+1}p_i\left(1-\left(1-\dfrac{m}{2m+1}\times p_i\right)^{j-1}\right)\dfrac{m-1}{2}

其中中间的部分为 i 至少被赋值过一次的概率，用等比数列优化计算即可做到 \mathcal{O}(n\log n)。