ABC174 F - Range Set Query (600)
最初の考察
愚直にやると$ O(NQ)
セグ木にsetを乗せると$ O(\log N Q)くらいになるのでは?
マージされるsetの作成が重いのかTLE
次の考察
分割統治してそれぞれの範囲で含まれる球の種類を持っておく
全部で持つと$ O(NQ)の空間計算量になり駄目
時間計算量が$ O(\log N Q)、空間計算量が$ O(N \log N)になって間に合うのでは?
立っているbitの計算に$ O(N)かかるので駄目
解説の方法
クエリを$ rの昇順に並び替える
自身が何番目のクエリか記録が必要
それぞれのクエリ毎に以下を行う
$ r以下の範囲でそれぞれの色で最も右にある位置を記録しておく
Binary Indexed Treeで上の位置を記録する
値が更新された場合は前の位置を消去する
自身の範囲内でBIT上で何個立っているかをカウントする
全ての値がBITに追加され、クエリ毎に範囲の和を計算するので$ O((N+Q)\log N)