[AtCoder is All You Need]ABC 276 F - Solution

2022-11-05 22:52 作者:故寓诸无竟 0人读过 | 我要投稿

我加了一个假问题

问题简述

给定一个长为 $n$ 的序列 $a$ 。考虑其前缀序列 $a_%7B1%5Csim%20i%7D$ ，从中放回地随机抽样两次，记这两次所得元素的最大值的期望为 $b_i$ 。求整个序列 $b$ 。

原题目链接：https://atcoder.jp/contests/abc276/tasks/abc276_f

思路1

最开始不知道为什么，认为只需要求 $b_n$ 。这样的话随便怎么乱搞都可以，所以我直接求了分布函数（，如果 $Z%3Dmax%5C%7BX%2CY%5C%7D$ ，那么 $F_Z(z)%20%3D%20F_X(z)%20F_Y(z)$ 。不出意外各大高校概率统计都会说这个。这里由于 $X$ 和 $Y$ 是同一个分布，所以 $F_Z(z)%20%3D%20F_X%5E2(x)$ ），然后直接 $E%5BZ%5D%20%3D%20z%5Cbar%7BF%7D_Z(z)$ ，就得到了一个优秀的 $O(%5Cmax%5C%7Ba%5C%7D-%5Cmin%5C%7Ba%5C%7D)$ 的算法（指算 $b$ 的一个元素，所以总共是 $O(n(%5Cmax%5C%7Ba%5C%7D%20-%20%5Cmin%20%5C%7Ba%5C%7D))$ ，太高了）。

思路2

然后意识到不对劲。

事实上， $b_i$ 可以写成和 $a$ 下标相关的表达式：

$b_i%20%3D%20E%5BZ%5D%20%3D%20%20%5Cfrac%7B1%7D%7Bi%5E2%7D%20%5Csum_%7Bj%3D1%7D%5Ei%20%5Csum_%7Bk%3D1%7D%5E%7Bi%7D%20%5Cmax%20%5C%7Ba_j%2Ca_k%20%5C%7D%20$

通常面对这种表达式，考虑两个期望之间的差异比较合适，不难得到：

$b_i%20%3D%20%5Cfrac%7B(i-1)%5E2%7D%7Bi%5E2%7Db_%7Bi-1%7D%20%2B%20%5Cfrac%7B1%7D%7Bi%5E2%7D%20%5Cleft(%202%5Csum_%7Bj%3D1%7D%5E%7Bi-1%7D%20%5Cmax%5C%7B%20a_j%2Ca_i%20%5C%7D%20%2B%20a_i%20%5Cright)$

快速计算上式的瓶颈在于 $2%5Csum_%7Bj%3D1%7D%5E%7Bi-1%7D%20%5Cmax%20%5C%7B%20a_j%2Ca_i%20%5C%7D$ 项，不难想到分成过大和过小的两部分计算：

$2%5Csum_%7Bj%3D1%7D%5E%7Bi-1%7D%20%5Cmax%5C%7B%20a_j%2C%20a_i%20%5C%7D%20%3D%202%5Cleft(%20a_i%20%5Ccdot%20%7C%5Cmathcal%7BG%7D(i%2Ca_i)%7C%20%2B%20%20%5Csum_%7Bj%3D1%2Ca_j%5Cge%20a_i%7D%5E%7Bi-1%7Da_j%20%5Cright)$

其中 $%5Cmathcal%7BG%7D%20(i%2Ca_i)%20%3D%20%5C%7B%20j%20%7C%201%5Cle%20j%20%3C%20i%2C%20a_j%20%3C%20a_i%20%5C%7D$ 。一部分是比 $a_i$ 小元素的数目，一部分是比 $a_i$ 大的元素的和。