a1..an数値といくつかのクエリがあるとします[l, k] (1 < l, k < n)。[l, k]問題は、2 つの等しい数の間の間隔の最小距離を見つけることです。
例: (間隔 l,k は |...| として示されます)
1 2 2 |1 0 1| 2 3 0 1 2 3
回答 2 (101)
1 |2 2| 1 0 1 2 3 0 1 2 3
回答 1 (22)
1 2 2 1 0 |1 2 3 0 3 2 3|
回答 2 (303) または (323)
セグメント ツリーも考えましたが、クエリが複数のノード間で共有されている場合、各ツリー ノードの結果を結合するのは困難です。それらに参加する方法をいくつか試しましたが、見栄えが悪いです。誰かが私にヒントを与えることができますか？
明確化
回答ありがとうございます。問題は、クエリが多いため、o(n) が良くないことです。誤ってセグメント ツリーについて言及したわけではありません。[l, r]検索[l, r]SUMまたは複雑[l, r]MINな配列でクエリを実行します。log(n)ここで o(logn) に収まるように前処理を行うことはできますか?