二分图中的交叉数

Question

在二分图中，左边有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

我想知道如何像一些用户提到的那样，通过使用二进制索引树来解决这个问题。我用O(n^2)algo求解，得到Tle。

这不是家庭作业。昨天我学习了BIT，正在寻找一些问题，所以我遇到了这个。告诉我诀窍。请不要写整个程序。

Answer 1

按左节点的索引对边进行排序，然后按右节点的索引（对于相等的左索引）对边进行排序。查看右侧节点的索引。图中的每一个交叉对应于一对索引，在这个排序列表中排列不顺。你只需要数数这样的“不按顺序排列”的对就可以了。

将排序列表中右节点的每个索引依次插入到二叉索引树中。在每次插入之后，您可以在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(h))比使用二叉索引树的复杂度O(h*log(m))要大，但对于边数不大于节点数的稀疏图来说，它需要更少的内存，而且对高速缓存更友好，因此应该更快。

如果在合并过程中消除重复项，合并排序方法的复杂度可以提高到O(h*log(m))。为此，对（value,numberOfInstances）的对应用合并排序，其中相邻的相同值用适当的“numberOfInstances”组合到一个条目中。在最坏的情况下，对于第一个log(m)合并过程没有消除重复，这具有O(h*log(m))的复杂性；则在O(h)时间内快速消除重复项时,可保留多达log(n)次传递。

实现一个二进制索引树，对于给定的键可以返回它在树中的索引，从最大的值开始（最大的一个->索引0，第二大的->索引1，...)。然后在将每个元素插入到树中之后，请求它的索引--这将是排序列表中该元素左边的较大值的数目。

更多细节：二进制索引树可能被实现为搜索树，其每个节点都被后代节点的计数器所增强。不要为重复的元素创建单独的节点，只需为每个元素更新后代节点计数器。当查询某个键的索引时，首先要搜索树中对应于该索引的节点；然后对当前节点的每个祖先的直接右子代的所有计数器求和，包括当前节点本身的右子代，但不包括当前节点在其某些祖先的右侧的所有情况。