読者です 読者をやめる 読者になる 読者になる

問題解決の宝石箱

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

指定区間の最大値/最小値のインデックスを求めるクエリにたくさん答えたい part1

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

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

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