急に思いついたので実装してみたらなんか速かった。 アイデア 集合の要素数の最大値が高々 であるとして, 個の集合 を次のようなルールにしたがって管理することを考えます。 各 の要素数は高々 である。 かつ なら である。 かつ なら である。 このとき、各 の最大値 を持つことで挿入削除が time、インデックスアクセスが time で行えます。 insert ルールより、 は単調増加です。したがって、(挿入する要素の値) となるような最小の を二分探索し、これを とします。 次に、 に要素を挿入し、 となるまで以下の操作を行います。 の最大値(dequeの末尾)をコピーし削除する。 を更新。…