問題概要
$N \ $個の整数$ \ a_1,a_2,\ldots,a_N \ $がある。
各整数$ \ i \ (1 \leq i \leq N) \ $について$ \ a_1,a_2,\ldots,a_i \ $の中央値を小数点以下切り捨てで求めよ。
制約
- $1 \leq N \leq 5 \times 10^5$
- $0 \leq a_i \leq 10^9$
解説
優先度付きキューを$ \ 2 \ $つ使用します。ここでは$ \ 2 \ $つのキューを$ \ que_1,que_2 \ $とします。
$que_1 \ $には$ \ A \ $の中央値以下の値が、$que_2 \ $には中央値以上の値が入ってるようにします。 また、$que_1の要素数 \leq que_2の要素数 \ $が常に成り立つようにします。
このとき$ \ A \ $の中央値は、$A \ $の要素数が偶数のとき$ \ \frac{que_1の最大値 + que_2の最小値}{2}$。 奇数のとき$ \ \frac{que_1の最大値}{2} \ $となります。
$a_i \ $を追加する際に、$i \ $が奇数であれば追加後の$ \ A \ $の要素数は偶数です。
$a_i \ $が$ \ que_2 \ $の最小値より大きいのであれば$ \ a_i \ $を$ \ que_2 \ $に追加します。 ただし、要素数の条件を満たすようにするため、まず$ \ que_2 \ $の最小値を削除し、$que_1 \ $に追加します。 その後$ \ a_i \ $を$ \ que_2 \ $に追加します。
そうでない場合$ \ a_i \ $は$ \ que_1 \ $に追加します。
$a_i \ $を追加する際に、$i \ $が奇数であれば追加後の$ \ A \ $の要素数は奇数です。
$a_i \ $が$ \ que_1 \ $の最大値より大きいのであれば$ \ a_i \ $を$ \ que_1 \ $に追加します。 ただし、要素数の条件を満たすようにするため、まず$ \ que_1 \ $の最大値を削除し、$que_2\ $に追加します。 その後$ \ a_i \ $を$ \ que_1 \ $に追加します。
そうでない場合$ \ a_i \ $は$ \ que_2 \ $に追加します。
このようにこの問題は計算量$ \ O(N \log N) \ $で解くことができます。
