如何在O（nlogn）时间复杂度下完成

Question

我在考试中提出了一个问题，我不得不提出一个有效的算法。问题是这样的：

我们有一些对象具有两个属性：

H = <1,1000000> 
R = <1,1000000> 

如果H1>H2和R1>R2我们可以插入一个对象到另一个。输入包含H和R对，每行一对。如果当前对象可以插入任何以前的对象中，我们至少选择这样的对象，然后我们销毁它们。打印输出中左侧对象的数量。

我不知道如何解决这个问题在O(n.log(n))时间复杂性使用二叉搜索树或分段树，或与fenwick树。

在此先感谢。

Answer 1

与fenwick树的解决方案，如下所示;

• 让我们整个阵列通过R在第一排序（现在，我们不关心H），并指定每个项目的令牌（等于它的排序数组中的位置）。我们回到原始数组。我们将在给定的数组上运行一次扫描。比如说，我们有一个fenwick树，它只会代替H而不是累积和，从而存储最大值（从开始到那个位置）。
• 对于一个项目，比方说，我们无法将它放入其他项目。然后我们将它插入树中。我们将插入等于它的标记的位置。
• 所以，现在，我们有一个fenwick树，它只包含我们处理过的物品，直到现在。其他值为0.树中的项目排列顺序为R。
• 现在，如何找出我们是否可以将当前项目适合其他对象？我们实际上可以在fenwick树上为当前项目的H运行二分查找（上限）。而且，由于这些项目已经按R排序，而不是整棵树，我们需要在有效范围内进行搜索。
• fenwick树中的二进制搜索可以在O(log(n))中完成。查看查找索引，给定累积频率部分this文章。