1

アルゴリズムの問​​題の解決策を理解するのに苦労しています

特に、コードのこの部分の方法や理由がわかりません

s += a[i];
total += query(s);
update(s);

各ポイントの左下象限にあるポイントの総数を計算できます。

誰か詳しく教えてください。

4

1 に答える 1

1

平面問題の類推として、次のことを考慮してください。

  1. 点 (a, b) が (x, y) の左下象限にあるには、a < x & b < y; したがって、(i, P[i]) の形式の点は、i < j および P[i] < P[j] の場合、(j, P[j]) の左下象限にあります。
  2. 昇順で反復する場合、以前に考慮されたすべてのポイントは、現在 (i, P[i]) と比較して左側にあります。
  3. したがって、これまで考えられてきた P[i] より少ないすべての P[j] を見つけるだけで済みます。

*現在のポイントとは、引用した for ループの現在の繰り返しで考慮されているポイント、つまり (i, P[i]) を指します。

別の配列 C[s] を定義しましょう:

C[s] = Number of Prefix Sums of array A[1..(i - 1)] that amount to s

したがって、#3 の解は合計になります ... C[-2] + C[-1] + C[0] + C[1] + C[2] ... C[P[i] - 1] 、つまり C[P[i]] の前置和

BIT を使用して C のプレフィックスの合計を格納し、クエリを次のように定義します。

query(s) = Number of Prefix Sums of array A[1..(i - 1)] that amount to a value < s

これらの定義を使用すると、指定されたコードの s によって、現在のインデックス i (P[i]) までのプレフィックスの合計が得られます。total は答えを構築し、update は単純に P[i] を BIT に追加します。

このメソッドをすべての i に対して繰り返す必要があるため、for ループになります。

PS: バイナリ インデックス ツリー ( http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees ) と呼ばれるデータ構造を操作に使用します。よくわからない場合は、リンクを確認することをお勧めします。

編集: 配列 S と値 X が与えられます。S を 2 つの互いに素な部分配列に分割して、L が X より小さい S のすべての要素を持ち、H が X 以上の要素を持つようにすることができます。

A: All elements of L are less than all elements of H.

S の任意のサブシーケンス T は、L のいくつかの要素と H のいくつかの要素を持ちます。L の p 個の要素と H の q 個の要素を持つとしましょう。T を並べ替えて T' を与えると、L のすべての p 個の要素が の q 個の要素の前に現れます。 AのせいでH。

Median being the central value is the value at location m = (p + q)/2

証明として、q >= p を持つことは中央値が X にあることを意味すると考えるのは直感的です: T' の位置 [1..p] の値は L に属します。 m は p より大きくなければなりません:

m > p
(p + q)/2 > p
p + q > 2p
q > p
B: q - p > 0

q - p を計算するには、T' のすべての要素が L ( < X ) に属している場合は -1 に置き換え、H ( >= X ) に属している場合は +1 に置き換えます。 T は {-1, -1, - のようになります。 1... 1, 1, 1} p 回 -1 と q 回 1 を持ちます。T' の合計は次のようになります。

Sum = p * (-1) + q * (1)
C: Sum = q - p

この情報を使用して、B の値を見つけることができます。

すべてのサブシーケンスは {A[i], A[i + 2], A[i + 3] ... A[j + 1]} の形式です. 連続しているため. A[i] から A への合計を計算するには[j + 1]、私は P[i] = A[1] + A[2] + .. A[i - 1] A[i] から A[i] までのサブシーケンスの合計で A[i] のプレフィックス和を計算できます。 A[j] は P[j] - P[i] として計算できます (j は j と i より大きい) C と B を念頭に置いて、次のように結論付けます。

Sum = P[j] - P[i] = q - p  (q - p > 0)
P[j] - P[i] > 0
P[j] > P[i]

j > i および P[j] > P[i] を与える各解について、中央値 >= X

要約すれば：

  1. すべての A[i] を X より小さい場合は -1 に、そうでない場合は -1 に置き換えます
  2. A[i] のコンピュータ プレフィックスの合計
  3. 各ペア (i, P[i]) について、その左下象限にあるペアをカウントします。
于 2014-05-17T17:00:55.890 に答える