問題概要
N 個の整数 a1,a2,…,aN がある。
各整数 i (1≤i≤N) について a1,a2,…,ai の中央値を小数点以下切り捨てで求めよ。
制約
- 1≤N≤5×105
- 0≤ai≤109
解説
優先度付きキューを 2 つ使用します。ここでは 2 つのキューを que1,que2 とします。
que1 には A の中央値以下の値が、que2 には中央値以上の値が入ってるようにします。 また、que1の要素数≤que2の要素数 が常に成り立つようにします。
このとき A の中央値は、A の要素数が偶数のとき que1の最大値+que2の最小値2。 奇数のとき que1の最大値2 となります。
ai を追加する際に、i が奇数であれば追加後の A の要素数は偶数です。
ai が que2 の最小値より大きいのであれば ai を que2 に追加します。 ただし、要素数の条件を満たすようにするため、まず que2 の最小値を削除し、que1 に追加します。 その後 ai を que2 に追加します。
そうでない場合 ai は que1 に追加します。
ai を追加する際に、i が奇数であれば追加後の A の要素数は奇数です。
ai が que1 の最大値より大きいのであれば ai を que1 に追加します。 ただし、要素数の条件を満たすようにするため、まず que1 の最大値を削除し、que2 に追加します。 その後 ai を que1 に追加します。
そうでない場合 ai は que2 に追加します。
このようにこの問題は計算量 O(NlogN) で解くことができます。