AT_ABC276F Double Chance 题解

题意

给定长为 $N$ 的一列数 $A_1, A_2, \cdots, A_N$。对于 $K = 1, 2, \cdots, N$，分别求出从前 $K$ 个数里先后两次等概率随机取出一数并放回，两数较大值的期望。

题解

由题目描述和期望的定义知，对于一个固定的 $K$，答案是 $\dfrac{\sum_{i=1}^K\sum_{j=1}^K\max(A_i,A_j)}{K^2}$。

$K = 1$ 时答案显然是 $A_1$。接下来，考虑增量计算答案。

分母的处理是平凡的。考察分子。

当 $K = K_0$ 的结果已计算，现在令 $K = K_0 + 1$，并加入 $A_{K_0 + 1}$ 时，分子增加了以下三个部分：

• 对于所有先前加入的 $A_i \le A_{K_0 + 1}$，$A_{K_0 + 1}$ 都会作为较大值在 $(i, K_0 + 1)$ 和 $(K_0 + 1, i)$ 处各贡献 $1$ 次；

• $A_{K_0 + 1}$ 会在 $(K_0 + 1, K_0 + 1)$ 处贡献 $1$ 次；

• 对于所有先前加入的 $A_i > A_{K_0 + 1}$，$A_i$ 都会作为较大值在 $(i, K_0 + 1)$ 和 $(K_0 + 1, i)$ 处各贡献 $1$ 次。

第一种贡献需要知道先前加入的 $A_i \le A_{K_0 + 1}$ 的 $i$ 的数目，第三种贡献需要知道先前加入的 $A_i > A_{K_0 + 1}$ 的 $A_i$ 的和。任写一种支持维护前后缀权值和的数据结构即可。

AT 提交记录