必ずしもソートされていない配列があります。Qクエリを実行する必要があります。クエリは次のようになります。配列とインデックスIが与えられた場合、A [I]> A [j]となるように、その配列に含まれるすべての要素をインデックスi +1からnに更新する必要があります。クエリは相互に依存しています。つまり、クエリ1に加えられた変更は、クエリ2に反映されます。
すべてのクエリに対して行われる変更は次のとおりです。
for j=I+1 to N:
if A[j]<A[I]:
A[j]=0
私はその問題にどのように取り組むべきか分かりません。バイナリインデックスツリーの線に沿って何かを考えています。しかし、私にはわかりません。ヒントでは、高度なソートアルゴリズムを使用するように指示されています。
ここにO（（q + n）log n）アプローチがあります：
クエリごとにセグメントツリーでn個の更新を行う可能性があるため、これは遅いように思われるかもしれませんが、各要素は最大で1回マークされるため、最悪の場合はO（（q + n）log n）です。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加