問題解決の宝石箱

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

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

長さ { 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つ紹介する。

続きを読む