4

前回の 2 つの質問「Range Minimum Query アプローチ (ツリーから制限付き RMQ へ)」と「Range Minimum Query アプローチ (最終ステップ)」の続きです。

私はTopCoder でこのチュートリアルに従いました。アプローチは最後のセクションで紹介されています。

すべてが完了したと仮定すると、クエリの準備が整いました。チュートリアルによると、これは私がすべきことです：

i と j は同じブロックにあるため、P と T で計算された値を使用します。

たとえば、次のようなブロックがあるとします。

000111

最小値はもちろん 3 番目の 0 にありますが、i と j が 4 と 6 のようであれば、3 番目の 0 は照会された基準にはありません。私の理解は間違っていますか？

i と j は異なるブロックにあるため、3 つの値を計算します。P と T を使用して i から i のブロックの終わりまでの最小値、A' で事前に計算されたクエリを使用して i と j のブロックの間のすべてのブロックの最小値、およびj のブロックの先頭から j まで、ここでも T と P を使用します。最後に、計算したばかりの 3 つの値を使用して全体の最小値になる位置を返します。

i から i のブロックの終わりまでの最小値と、j のブロックの開始から j までの最小値を計算するのはなぜですか? どちらも答えは i...j の外にあるのではないですか？また、最後の質問のように完全に適合しない場合の方法。

4

1 に答える 1

3

最小値はもちろん 3 番目の 0 にありますが、i と j が 4 と 6 のようであれば、3 番目の 0 は照会された基準にはありません。私の理解は間違っていますか？

アイデアは、可能なすべてのブロック内のすべてのインデックスのペアのRMQ を事前に計算することです。その結果、そのブロック内でクエリするインデックスに関係なく、ブロック内の 2 つの値の RMQ を O(1) 時間で常に読み取ることができるはずです。質問に記載されている場合、インデックス 4 と 6 にブロックの最小値が含まれていないという事実は真実ですが、無関係です。インデックス 4 と 6 の RMQ は既に計算済みです。

i から i のブロックの終わりまでの最小値と、j のブロックの開始から j までの最小値を計算するのはなぜですか? どちらも答えは i...j の外にあるのではないですか？また、最後の質問のように完全に適合しない場合の方法。

この図を考えてみましょう:

+------+------+------+------+------+------+
| ?i?? | ???? | ???? | ???? | ??j? | ???? |
+------+------+------+------+------+------+
   ^                            ^
   i                            j

RMQ(i, j) を解きたい場合、最小値は次の 3 つの場所のいずれかにある可能性があります。

  • i と同じブロック内で、そのブロック内の i の位置からそのブロックの末尾までのインデックスで、
  • j と同じブロック内で、そのブロック内の 0 から j の位置までのインデックスで、または
  • 中央の 3 つのブロックのうちの 1 つのどこかにあります。

このアルゴリズムは、事前計算されたテーブルを使用して最初の 2 つのケースの問題を解決し、次に他のアルゴリズムを使用して 3 番目のケースの問題を解決します。これら 3 つの最小値が答えになるはずです。

お役に立てれば！これは決して簡単なアルゴリズムではありません。サポートが必要な場合は、ここでさらに質問してください。

于 2013-02-09T04:51:35.120 に答える