ABC276 F - Double Chance (500)
$ k枚のカードで考えると、カードの数を昇順にソートするとその数が最大値となる確率は$ \frac{1}{k^2},\frac{3}{k^2},\cdots,\frac{2k-1}{k^2}となる
これを$ k毎に求め直すと$ \Omega(N^2)
前から見て確率を更新するのは配列に挿入が必要になるので後ろから見ていく
最終的な期待値はAを昇順にソートすれば求まる
ソートした配列を入れたセグ木と削除されたかどうかをもつセグ木を用意する
逆順で以下を行う
今見ている値がソートした配列で何番目かを取得
そこが既に前で削除済みなら削除していないところまで後ろに移動
これを毎回愚直に行うと$ \mathcal{O}(N^2)になるので、どこまで移動したかを元の位置で保存しておく
そこを削除済みにする
期待値を再計算するために分母分をかける
今見ている位置より後ろは分子だけを見ると確率が2減るので、今見ている位置より後ろの和に2をかけたものを引く
今見ている位置は0になるのでそうなるように値をかけて引く
かける値については左にある削除された回数の和を使って求める
期待値を再計算するために新しい分母で割る
ソートした配列のセグ木で今の位置の値を0にする
今の位置の削除された回数を1にする
各位置でセグ木の操作をしているので$ \mathcal{O}(N \log N)