6

前回の質問「範囲最小クエリアプローチ（ツリーから制限付きRMQまで） 」からの続き（読むことをお勧めします）

繰り返しになりますが、TopCoderに関するこのチュートリアルから、あちこちでいくつか質問があります。誰かがそれらを解決してくれることを願っています。

したがって、RMQ（範囲最小クエリ）問題をLCA（最小共通祖先）問題に変換してから、元に戻すと、単純化された配列を作成できます。（両方の変換はチュートリアルにあり、簡略化された配列は「LCAからRMQへ」で説明されている配列Lです）

とにかく、私はオイラーツアーを使用してその配列を取得できます。これがすべての計算の中心的な部分です。

まず、配列全体を1と-1だけで構成することで、さらに単純にする必要があります。これが私が行うことですLs[i] = L[i] - L[i-1]。

2番目のステップは実際にはパーティション化であり、それは十分に単純ですが、私を混乱させるこの3番目のステップがあります。

A'[i]をAのi番目のブロックの最小値とし、B[i]をAのこの最小値の位置とします。

Aはこの文のL配列を参照しているため、最小値は常に1または-1になり、複数の1と-1が存在することになります。これで計算が簡単になるとは思わないので、混乱します。

4番目のステップ、

ここで、セクション1で説明したSTアルゴリズムを使用してA'を前処理します。これには、O（N / l * log（N / l））= O（N）の時間とスペースが必要です。

A'が1と-1の記録しか保持しない場合、それに対して何もすることは役に立たないように思われます。

最後のステップ、

テーブルPにインデックスを付けるには、Aの各ブロックのタイプを前処理し、配列T [1、N/l]に格納します。ブロックタイプは、-1を0に、+1を1に置き換えて得られる2進数です。

どういう意味ですか？それぞれの組み合わせを計算するには？のように、000--..... 001？

複数の質問のように見えますが、誰かがこれらの最後のステップを案内してくれることを望んでいました。ありがとう！

4

1 に答える 1

5

うまくいけば、これは物事を説明するのに役立ちます。

Aはこの文のL配列を参照しているため、最小値は常に1または-1になり、複数の1と-1が存在することになります。これで計算が簡単になるとは思わないので、混乱します。

著者はここで用語を混同していると思います。この場合、配列Aは、-1と+1に前処理される前の元の値の配列を指していると思います。元の配列の各ブロックに対して最小値が計算されると、RMQの実行が大幅に高速化されるため、これらの値は横になっていると便利です。これについては後で詳しく説明します。今のところ、+1と-1の値について心配する必要はありません。それらは後で登場します。

A'が1と-1の記録しか保持しない場合、それに対して何もすることは役に立たないように思われます。

それは本当だ。ただし、ここでA'は、-1と+1の値に前処理される前の各ブロックの最小値を保持しているため、これは実際には解決すべき興味深い問題です。繰り返しになりますが、-1と+1のステップはまだ機能していません。

テーブルPにインデックスを付けるには、Aの各ブロックのタイプを前処理し、配列T [1、N/l]に格納します。ブロックタイプは、-1を0に、+1を1に置き換えて得られる2進数です。

ここで-1と+1の値が出てきます。このステップの背後にある重要なアイデアは、ブロックサイズが小さい場合、ブロック内に-1と+1の可能な組み合わせがあまりないということです。たとえば、ブロックサイズが3の場合、可能なブロックは次のようになります。

---
--+
-+-
-++
+--
+-+
++-
+++

ここでは、+と-を使用して+1と-1を意味しています。

あなたが読んでいる記事は次のトリックを与えます。-1と+1を使用するのではなく、バイナリ0と1を使用します。これは、可能なブロックが

000 = 0
001 = 1
010 = 2
011 = 3
100 = 4
101 = 5
110 = 6
111 = 7

このスキームの利点は2つあります。まず、ブロックの数は有限であるため、可能なブロックごとに、そのブロック内のインデックスの任意のペアに対するRMQ回答を事前に計算することができます。次に、各ブロックは整数として解釈できるため、これらの質問に対する回答を整数でキー設定された配列に格納できます。各整数は、ブロックの-1と+1の値を0と1に変換することで得られるものです。

お役に立てれば！

于 2013-02-09T03:54:45.993 に答える