削除可能集合で不等号条件
要求
削除可能な集合$ \{x\} から不等号で表現された条件$ x \ge x_0を満たすものを列挙したい
例えばソート済み配列なら二分探索で不等号条件を満たす境界を対数オーダーで見つけられる
しかし配列からの削除は線形オーダー掛かってしまう
削除が高速なリンクトリストでは、ランダムアクセスができないので二分探索できない
解法
フェニック木を使う
値域は0/1で、値の存在不在を表現
x0以下の範囲に対する和sを対数オーダーで計算し、それから和がs+1になる点を対数オーダーで二分探索すれば良い
削除可能集合で不等号条件
問題変換