n-knuu's logs

憧れ駆動。だいたい競プロ

区間 mex クエリ問題

集合の中に含まれない最小の数を求める操作は mex(minimum exclude に由来) と呼ばれている。

Mex (mathematics) - Wikipedia

区間に対する mex を求める問題を見かけたので備忘録として書いておく。

問題

はじめ、集合 S は空集合であるとする。

Q 個のクエリが与えられ、各クエリは以下の3つの形式のいずれかである。

  1. 1 x: xを集合Sに加える
  2. 2 x: xを集合Sから取り除く
  3. 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. 1 x: x に対応する segment 木の葉を x から INF に置き換える
  2. 2 x: x に対応する segment 木の葉を INF から x に置き換える
  3. 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] みたいなクエリも簡単に対応可能。