区間がたくさん与えられるので、別に与えられる区間に含まれるものはいくつあるか？というクエリに効率良く答える方法を、オフライン版、オンライン版共に紹介。

hama-du-competitive.hatenablog.com 前回の記事の最後で紹介した練習問題の解答編。問題を整理して再掲する。 長さ の数列 が与えられる。クエリに 個答えよ。 全ての問題において、制約は以下の通り。 数列の長さ： 要素の値： クエリの数： 問題1 i 番目…

区間内の最大値/最小値のインデックスを求めるRMQの実装を求めています。— tookunn (@tookunn_1213) October 6, 2016 この問題を以下のように定式化した。効率よく解けるだろうか？ 長さ の数列 が与えられる。以下のクエリに 個答えよ。 クエリ1 : i 番目の…

長さ の数列 が与えられる。以下のクエリにたくさん答えよう。 クエリ : 区間 中に出現する数の種類数を求めよ 以下の制約で、効率的に解くことはできるだろうか？ 数列の長さ： 要素の値： クエリの数： 以下、解法を3つ紹介する。