区間 mex クエリ問題
集合の中に含まれない最小の数を求める操作は mex(minimum exclude に由来) と呼ばれている。
区間に対する mex を求める問題を見かけたので備忘録として書いておく。
問題
はじめ、集合 S は空集合であるとする。
Q 個のクエリが与えられ、各クエリは以下の3つの形式のいずれかである。
1 x
: xを集合Sに加える2 x
: xを集合Sから取り除く3 l r
: [l, r]である整数xのうち、集合Sに含まれない最小のxを出力する
与えられたQ個のクエリを順に処理せよ。
制約
- 1 <= Q <= 105
- -109 <= x <= 109
- -109 <= l <= r <= 109
- 2 番目のクエリにおいて、x は必ず S に含まれる
- 3 番目のクエリにおいて、[l, r] である整数のうち集合 S に含まれないものが必ず存在する。
解法
この問題はクエリ先読み(+座標圧縮)+segment 木 (range min query) で解ける。 (2018-03-02 追記: asi1024さんよると、区間を管理する set と set の lower_bound でも同様に解けるそうです。)
segment 木の基礎は蟻本中級編を読もう!
まずクエリを先読みし、x, l, r と x - 1, x + 1 を持つ配列を作り、ソートして重複を取り除く。
次にこの配列を葉としてもつ segment 木 (range min query) を作る。
あとはこの segment 木を元に以下のようにクエリを処理すればよい。
1 x
: x に対応する segment 木の葉を x から INF に置き換える2 x
: x に対応する segment 木の葉を INF から x に置き換える3 l r
: l, r に対応する葉の区間の range min query の結果を出力する
計算量
O(Q log Q)
コード
類題とか
Introduction to Segment Tree C: Big Range Query
maximum exclude の場合は min を max に、INF を -INF にすればよい。
また、[left, ∞) とか (-∞, right] みたいなクエリも簡単に対応可能。