問題解決の宝石箱

競技プログラミング/数学ネタ置き場

与えられた数列の区間中の種類数を求めるクエリにたくさん答えたい

長さ { N } の数列 { a_{1}, a_{2}, ... , a_{N} } が与えられる。以下のクエリにたくさん答えよう。

  • クエリ : 区間 { 1 \leq L\ \leq R\ \leq N } 中に出現する数の種類数を求めよ

以下の制約で、効率的に解くことはできるだろうか?

  • 数列の長さ:{ 1 \leq N \leq 10^5 }
  • 要素の値:{ 1 \leq a_{i} \leq 10^5 }
  • クエリの数:{ 1 \leq Q \leq 10^5 }

以下、解法を3つ紹介する。

解法1 : Mo's algorithm

事前にクエリを特別な方法でソートしておけば、区間を左右に動かすだけで簡単に求まる。 この記事では深入りしないが、ざっくり説明すると

  • 数列を  { \sqrt{N} } 個のバケットに分け、クエリを < {L} のバケット番号,  {R}> でソート
  • 配列 d[x] : 値 x を現在の区間でいくつ持ってるか を用意 (0で初期化)
  • ソートしたクエリを順番に処理するとき、L/Rの増減に合わせて以下の処理をする。
    • d[(増えた位置の数 or 減った位置の数)] の値を増減し、d[x] が 1 に増えた or 0 に減ったら現在の答えに ±1

計算量は  { O(N\sqrt{N}) }

解法2 : もう少しマシな方法

  • まず、クエリを  {R} の昇順にソートする。
  • 配列 lastAppeared[x] : 値 x が最後に出現した位置 を用意。
  •  長さ  {N} の BIT を用意する。lastAppeared[x] の位置に +1 していく
  • ソートしたクエリを順番に処理する
    • 右端の位置 R が右に伸びたら、それぞれについて lastAppeared[a[R]] = R と更新。それに合わせて、対応する BIT の位置に -1, +1 する。+1 を右に移動するイメージ。
    • クエリに答える。答えは BIT.sum(L[i], R[i])

f:id:hama_DU:20160930235147p:plain

↑求めたいクエリのRの右端の値が伸び、a[8], a[9] が加わるとする。

f:id:hama_DU:20160930235201p:plain

↑するとlastAppeared[1] = 8, lastAppeared[2] = 9 となり、対応する位置のBITの値も更新。

計算量は  { O(Q\log{Q} + N\log{N}) }。ソースコードは以下。 https://github.com/hamadu/competitive-programming-snippets/blob/master/src/utils/DistinctNumberRange1.java

解法3 : オンラインアルゴリズム

上2つで紹介した方法はどちらもクエリを先読みするタイプのアルゴリズムだが、これをオンラインで解く巧妙な方法を教わったので説明する。

  • まず、同じ数をちょうど2つ含む最小の区間をすべて列挙する。(以降、これを「数区間」と呼ぶ)
  • それぞれのクエリに対しては、(クエリ区間長) - (クエリ区間に完全に含まれる数区間の数) が答えとなる。

ある数区間がクエリ区間に完全に含まれるということは、クエリ中に同じ数が 2つ 含まれているということ。なのでこれを引けば答えが求まるというシンプルなアイデア。

f:id:hama_DU:20160930235103p:plain

区間列が与えられ、指定区間に含まれる区間の数を求める問題は色々なやり方がありそうなので、別途調査して発表予定。

2017/04/22追記: 区間クエリの記事を書きました。

competitive.hamadu.net

計算量は  { O(N\log{N}) }ソースコードは以下。 https://github.com/hamadu/competitive-programming-snippets/blob/master/src/utils/DistinctNumberRange2.java

2017/04/22追記: ↑のコードは内部でクエリをソートしてるので、オンラインになってませんでした。オンラインで求める方法は追加記事をご覧ください。