優秀な成績と低いジャーランクの学生数

Question

私たちは、すべての生徒のcgpa（大学の成績）とjeeランク（入学試験のランク）を持つn人の学生を与えられます。 すべての生徒について、cgpaが良いがjeeランクが悪い生徒の数を計算する必要があります。

（X1、Y1）、（X2、Y2）···（XI、YI）...（XN、YN）私は、我々はノー計算する必要がそれぞれの

。 xj> xiとyj> yi（悪いランクはランクが悪い）の012の方が良いでしょう。

私は以下のnlognアルゴリズムを考え出すことができました。 cgpaを減らして並べ替えます。 ここから左からスキャンを開始します。 これまでにスキャンされた生徒をバランスのとれたバイナリツリーに維持します（ジーランクに従います）。 次の生徒のために、バランスのとれたバイナリツリーを照会することによって、より高いランクで既にスキャンされた生徒の数を調べるだけです。

バランスのとれたbstを維持する方法がわかりません。返信することはできません。 O（logn）のkより小さい要素の数。我々はnoを維持する必要があります。各ノードのサブツリー内のノードの数。しかし、それを行う方法？

上記のいずれかの助けか、別のアルゴリズム、おそらくDPを提供してください。

Answer 1

バランスのとれたバイナリツリーをコーディングする必要がない場合は、Binary Indexed Tree（別名BITまたはFenwick Tree）を見てください。それは<簡単な行でコード化することができます。 Hereは、私がフェンウィック・ツリーに書いたブログ・ポストです。