inq*_*ive 5 sorting algorithm graph-theory overlapping data-structures
任何人都可以建议我这个算法.
您将获得x轴上N段的起点和终点.即使在它们的边缘上,也可以通过垂直于它们的两条线来触摸这些段中的多少个？
样本输入:
3
5
2 3
1 3
1 5
3 4
4 5
5
1 2
1 3
2 3
1 4
1 5
3
1 2
3 4
5 6
样本输出:
Case 1: 5
Case 2: 5
Case 3: 2
说明:
约束:
1 ? N ? 10^5
0 ? a < b ? 10^9
假设我们有一个有效支持以下操作的数据结构：
添加一段。
删除一个段。
返回覆盖一个点（即“最佳”点）的最大线段数。
如果有这样的结构，我们可以通过以下方式有效地使用初始问题：
让我们创建一个事件数组（一个事件用于每个段的开始，一个事件用于结束）并按 x 坐标排序。
将所有段添加到神奇的数据结构中。
迭代所有事件并执行以下操作：当段开始时，将当前覆盖的段数加一并将其从该数据结构中删除。当一个段结束时，将当前覆盖的段数减一，并将该段添加到神奇的数据结构中。在每个事件之后，用当前覆盖的段数的值（它显示了与当前事件对应的点覆盖了多少段）加上上述数据结构返回的最大值（它显示了我们如何可以以最佳方式选择另一个点）。
如果这个数据结构可以执行 中的所有给定操作O(log n)，那么我们就有一个O(n log n)解决方案（我们对事件进行排序，并对排序后的数组进行一次传递，为每个事件对此数据结构进行恒定数量的查询）。
那么我们如何实现这个数据结构呢？嗯，线段树在这里工作得很好。添加段就是向特定范围添加一个。删除一个段就是从特定范围内的所有元素中减一。获取最大值只是线段树上的标准最大值操作。因此，我们需要一个支持两种操作的线段树：向范围添加一个常量并获取整个树的最大值。每次查询都可以及时完成O(log n)。
还有一点需要注意：标准线段树要求坐标很小。我们可以假设它们永远不会超过2 * n（如果不是这种情况，我们可以压缩它们）。