數叉口的在二分圖中，有在右側的左側和m個節點上n個節點。節點從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的解碼，可以使用分而治之算法來解決問題倒的數量，基於合併排序。詳見here。該方法具有比使用二元索引樹O（h * log（m））的複雜度更大的時間複雜度O（h * log（h）），但對於邊數不太大的稀疏圖節點，它應該更快，因爲它需要更少的內存並且更容易緩存。
歸併排序接近的複雜性，如果我們在合併過程中避免出現重複條目，可以提高到O（H *日誌（M））。爲此，請將合併排序應用於（value，numberOfInstances）對，其中相鄰的相同值通過適當的'numberOfInstances'組合成一個條目。在最壞的情況下，第一個log（m）合併過程不會消除重複，這具有O（h * log（m））的複雜度;那麼在O（h）時間內快速消除重複項時，最多可保留log（n）通過。
二進制索引樹使用詳情：
實現二進制索引樹，對於給定的密鑰可以在樹中返回它的指數，從最大的值開始（最大的一個 - >索引爲0，第二大 - >索引1，...）。然後在將每個元素插入樹中後，請求其索引 - 這將是排序列表中此元素左側較大值的數量。
更多細節：二進制索引樹可以實現爲搜索樹，每個節點所是由子孫節點的計數器增加。不要爲重複元素創建單獨的節點，只需更新每個元素的後代節點計數器。當被問及某個鍵的索引時，我們首先應該搜索一個節點，對應於樹中的這個索引;那麼我們應該將當前節點的每個祖先的當前右後裔的所有計數器加起來，包括當前節點本身的右後代，但不包括當前節點位於其一些祖先的右側的所有情況。
如果我明白你的問題正確，則
我們知道我們可以有NpowerM（讓這個值是X）兩套 之間的關係，如果我們可以找到設置它沒有交叉（可以說，我們發現它Y），那麼我們從X中減去Y即XY將以數學方式回答你的問題。 爲了找到Y，你在另一邊排列元素，在集合M上說，然後找到最長的遞增子序列（「http： //en.wikipedia.org/wiki/Longest_increasing_subsequence「）N和M這可以在O（nm）中完成，如果你足夠聰明，那麼你可以在O（NlogM）...時間內完成。爲解決方案的清晰度（類似的問題存在這裏「http://people.csail.mit.edu/bdean/6.046/dp/」點擊建立橋樑鏈接）
如果我正確理解了你的答案，它會失敗，並顯示如下圖：{（1,3），（2,4），（3,1），（4,2）}。 –
你應該再次考慮問題域。圖形節點沒有排序，所以你可以繪製上面沒有交叉的示例圖形（繪製你的兩列3,1,2,4和1,2,4,3））。所以你應該對節點的繪製方式施加幾何約束，或者要求最小數量的穿越（然後你應該改正你的例子）。 – flolo