誰でもこのタスクを手伝ってもらえますかhttp://www.spoj.com/problems/INVCNT/。最初はビットウェイで考えようとしますが、できません。このタスクの解決策を BIT で説明できる人はいますか。ビット - バイナリ インデックス付きツリー c++
2520 次
1 に答える
6
O(log n)クエリごとに次の問題を解決し、BIT を使用して更新する方法を知っていると仮定します。
Given an array A[1 .. n], implement the following functions efficiently:
query(x, y) = return A[x] + A[x+1] + ... + A[y]
update(x, v) = set A[x] = v
次のように現在の問題を解決できます。最初に、配列の値を正規化します。これは、すべての値が interval 内にあるように変換する必要があることを意味します[1, n]。これはソートで行うことができます。たとえば、5, 2, 8になり2, 1, 3ます。(注: 1、2、3 は、5、2、8 のソート順のインデックスです)
次に、各について、要素 でiいくつの反転が生成されるかを答えます。このためには、よりも前の要素の数を見つける必要があります。これは と同等です。A[i]j < iiiquery(A[i] + 1, n)
このクエリの後、次のことを行いますupdate(A[i], 1)。
これがどのように機能するかは次のとおりです。BIT 配列は最初はゼロで埋められます。この配列の位置にある 1 は、指定された配列の反復処理でk値に遭遇したことを意味します。kを呼び出すことで、それより前の要素でquery(A[i] + 1, n)いくつの反転A[i]が生成されるかがわかります。これは、これまで反復した要素よりも大きい要素の数を照会するためです。
これを見つけたらA[i]、訪問済みとしてマークする必要があります。これを行うA[i]には、BIT 配列の位置を更新し、1 を置きますupdate(A[i], 1)。
配列内の数値は to とは異なる1ためn、BIT 配列にはサイズがnあり、複素数は で対数になりnます。
最初の問題を解決する方法の詳細が必要な場合は書いてください。これは古典的なものであり、Google でコードを簡単に見つけることができるはずです。
注:この問題には、マージ ソートを使用した気の利いた解決策もあります。
于 2013-06-29T22:00:44.307 に答える