区間の種類数を答えるクエリ

Page content

問題設定

以下のようなクエリを考えます．

  • \(n\)要素の配列\(a\)が与えられる．
  • 各クエリでは、\([L, R)\)に含まれる数列\(a\)のdistinctな要素数を答える．
  • 配列への更新があっても解けると思いますが、配列への更新はない簡単な問題を考えます．

制約

  • \(1 \leq n \leq 10^5\)
  • \(0 \leq a_i < n\)
  • \(1 \leq Q \leq 10^5\)

考え方

  • \([L, R)\)の要素数から、重複している分を引けば良い．
  • 区間を左から見たときに、すでに出てきている要素を引くと考えても良い.
  • すでに\(x\)が出てきている: 1つ前の\(x\)が区間に含まれている．

方針

  • 各インデックス\(i\)について、\(a_i = a_j, j < i\)となる最大の\(j\)を\(p_i\)とする．
  • 区間内に\(p_i\)がすでに出てきた: \(L \leq p_i\)である、なので\([L, R)\)に含まれる区間\([p_i, i]\)の個数を\([L, R)\)の要素数から引けば良い．
  • 区間に含まれる区間の個数は2次元のセグメント木を用いると各クエリ\(O(log^2(N))\)で計算できるので各クエリ\(O(log^2(N))\)で種類数が分かる．
  • 2次元セグメント木において、全要素を陽に持つとMLEするので、クエリで必要なところだけ持つようにした方が良い．

類題

区間\([L, R)\)に対して、各要素\(k\)個まで数える．

  • \(p_i\)の定義を、"\(a_i = a_j, j < i\)となる\(k\)番目の\(j\)“に変更すれば良いです．

参考

必要な部分のみ作るセグメント木の例