特定の配列の場合、3つの要素の組み合わせを降順に数えます。

Question

プログラミングで過去の競争の問題を解決しているので、助けが必要です。問題を1つの文で説明します。 Nのサイズが10^5になる配列の配列があります。 2行目にはN個の要素があります。だから今度は配列から3つの要素を選ぶ方法を数えなければなりません。例は

N = 4であり、配列は190,180,170,168のように見えます。これらの3つの要素を選択する方法は4通りあります。 1.（190,180,168）2.（190,180,168）3.（190,170,168）および4.（180,170,168）

これはセグメントツリーで解決する必要がありますが、私はドンどの議論が私が木を作るべきか知っている。前もって感謝します。

Answer 1

1. 我々は、すべての数字は（そうでない場合、我々は彼らを「圧縮」することができます）[0, n - 1]範囲内にあると仮定することができます。

2. トリプルの中間要素の位置を修正しましょう。今度は、左から大きい方の要素の数を数え、右から小さい方の要素の数を掛けることができます。

3. 小さいインデックスの大きい要素の数をカウントするにはどうすればよいですか？我々はポイントでの更新と範囲の合計を必要とする

   tree = SegmentTree(0, n - 1) // for sum and add operations 
   for i = 0 ... n - 1 
       greaterLeft[i] = tree.getSum(a[i] + 1, n - 1) 
       tree.update(a[i], 1) 
   

4. 注：ここではそれを説明する擬似コードです。バイナリインデックスツリーは効率的に行うことができます（セグメントツリーより実装が簡単です）。