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木の基礎は蟻本中級編を読もう!

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

まずクエリを先読みし、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]みたいなクエリも簡単に対応可能。