2部グラフでは、左側にn個のノード、右側にm個のノードがあります。ノードは1からnおよび1からmの順序になっています。左側のノードは右側のノードに接続されています。すべてのノードが接続されているわけではありません。例：
1 is connected to 4
2 is connected to 3
3 is connected to 2
3 is connected to 1
グラフに交差点がいくつあるか知りたい（ここでは5つの交差点）。SPOJにも同様の問題があります
一部のユーザーが言及しているように、バイナリインデックスツリーを使用してこの問題を解決する方法を知りたいです。私はO（n ^ 2）アルゴリズムで解き、TLEを取得しています。
これは宿題ではありません。昨日私はBITを学び、いくつかの問題を探していたので、これに出くわしました。トリックを教えてください。プログラム全体を書かないでください。
左側のノードのインデックスでエッジを並べ替えてから、（左側のインデックスが等しい場合は）右側のノードのインデックスで並べ替えます。右ノードのインデックスを見てください。グラフの各交差は、このソートされたリストで順番に並んでいないインデックスのペアに対応しています。このような「順序が正しくない」ペアを数えるだけで済みます。
ソートされたリストから右ノードの各インデックスを順番にバイナリインデックスツリーに挿入します。挿入するたびに、O（log（m））時間内にツリーにすでに存在する大きなインデックスの数を確認できます。したがって、アルゴリズム全体の時間計算量は、O（h *（log（h）+ log（m）））：ソートの場合はO（h * log（h））、数値を計算する場合はO（h * log（m））です。インデックス反転の数（ここで「h」はエッジの数です）。基数ソートまたはバケットソートを使用して、これをO（h * log（m））に改善できます。
アップデート：
Android Decodedで気づいたように、反転数の問題は、マージソートに基づく分割統治アルゴリズムを使用して解決できます。詳細な説明はこちらをご覧ください。このアプローチは、バイナリインデックスツリーO（h * log（m））を使用する複雑さよりも時間計算量O（h * log（h））が大きくなりますが、エッジの数がノードの場合、必要なメモリが少なく、キャッシュに適しているため、高速になるはずです。
マージ中に重複するエントリを削除すると、マージソートアプローチの複雑さがO（h * log（m））に改善される可能性があります。これを行うには、マージソートを（value、numberOfInstances）のペアに適用します。ここで、隣接する同一の値が適切な'numberOfInstances'を持つ1つのエントリに結合されます。最悪の場合、最初のlog（m）マージパスで重複が排除されることはありません。これには、O（h * log（m））の複雑さがあります。その後、O（h）時間で重複がすぐに排除されると、最大log（n）パスが残ります。
バイナリインデックスツリーの使用法の詳細：
バイナリインデックスツリーを実装します。これは、指定されたキーに対して、最大値（最大値->インデックス0、2番目に大きい->インデックス1、...）から開始してツリー内のインデックスを返すことができます。次に、各要素をツリーに挿入した後、そのインデックスを要求します。これは、並べ替えられたリストでこの要素の左側にある大きな値の数になります。
詳細：バイナリインデックスツリーは、検索ツリーとして実装できます。検索ツリーの各ノードは、子孫ノードのカウンターによって拡張されます。重複する要素に対して個別のノードを作成するのではなく、各要素の子孫ノードカウンターを更新するだけです。あるキーのインデックスを求められたら、最初にツリー内のこのインデックスに対応するノードを検索する必要があります。次に、現在のノード自体の右の子孫を含む、現在のノードのすべての祖先のすぐ右の子孫のすべてのカウンターを合計する必要がありますが、現在のノードがその祖先の一部の右側にある場合はすべて除外します。
私があなたの質問を正しく理解していれば
交差のないセットを見つけることができれば（たとえば、Yとして見つけたとしましょう）、2つのセット間にNpowerM（この値をX）の関係を持たせることができます。次に、XからYを引くと、XYが答えになります。数学的に質問します。Yを見つけるには、反対側の要素を集合Mで並べ替えてから、NとMの最長増加部分列（ "http://en.wikipedia.org/wiki/Longest_increasing_subsequence"）を見つけます。 O（nm）で実行できます。十分に賢い場合は、O（NlogM）...時間で実行できます。解決策を明確にするために（同様の問題がここに存在します "http://people.csail.mit.edu/bdean/6.046/dp/"ブリッジの構築リンクをクリックしてください）