在二分图中，左边有 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 所注意到的，倒数问题可以使用基于 Merge Sort 的分治算法来解决。请参阅此处的详细说明。这种方法的时间复杂度 O(h * log(h)) 比使用二叉索引树 O(h * log(m)) 的复杂度要大，但是对于稀疏图来说，边的数量并不比边的数量大很多节点，它应该更快，因为它需要更少的内存并且对缓存更友好。
如果我们在合并期间消除重复条目，则合并排序方法的复杂性可能会提高到 O(h * log(m))。为此，将合并排序应用于 (value, numberOfInstances) 对，其中相邻的相同值通过适当的“numberOfInstances”组合到一个条目中。在最坏的情况下，第一个 log(m) 合并通道不会消除重复，这具有 O(h * log(m)); 的复杂性；然后在 O(h) 时间内快速消除重复项时，最多保留 log(n) 次。
二叉索引树使用细节：
实现一个二叉索引树，对于给定的键可以返回它在树中的索引，从最大值开始（最大的 -> 索引 0，第二大的 -> 索引 1，...）。然后在将每个元素插入树之后，请求它的索引 - 这将是排序列表中该元素左侧的较大值的数量。
更多细节：二叉索引树可以实现为搜索树，其每个节点都由后代节点的计数器增加。不要为重复元素创建单独的节点，只需更新每个元素的后代节点计数器。当询问某个键的索引时，我们应该首先在树中搜索一个与该索引对应的节点；那么我们应该对当前节点的每个祖先的直接右后代的所有计数器求和，包括当前节点本身的右后代，但排除当前节点位于其某些祖先右侧的所有情况。
如果我正确理解了你的问题
我们知道我们可以在两个集合之间有 NpowerM（让这个值是 X）关系，如果我们能找到没有交集的集合（假设我们发现它是 Y）然后我们从 X 中减去 Y，即 XY 将回答你数学上的问题..为了找到Y，你对另一边的元素进行排序，在集合M上说，然后找到N和M的最长增加子序列（“http://en.wikipedia.org/wiki/Longest_increasing_subsequence”）如果你足够聪明，可以在 O(nm) 内完成，那么你可以在 O(NlogM) ... time 内完成。为了明确解决方案（此处存在类似问题“http://people.csail.mit.edu/bdean/6.046/dp/”单击构建桥梁链接）