任何人都可以建议我为此的算法。
您将获得 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：我们将在点 2 和 4 处绘制两条与 X 轴相交的线（平行于 Y 轴）。这两条线将接触所有五个线段。
- 情况 2：即使一条线在 2 处穿过 X 轴，我们也可以触及所有点。
- 情况3：在这种情况下不可能触摸超过两个点。
限制条件：
1 ≤ N ≤ 10^5
0 ≤ a < b ≤ 10^9
假设我们有一个有效支持以下操作的数据结构：
添加一段。
删除一个段。
返回覆盖一个点（即“最佳”点）的最大线段数。
如果有这样的结构，我们可以通过以下方式有效地使用初始问题：
让我们创建一个事件数组（一个事件用于每个段的开始，一个事件用于结束）并按 x 坐标排序。
将所有段添加到神奇的数据结构中。
迭代所有事件并执行以下操作：当段开始时，将当前覆盖的段数加一并将其从该数据结构中删除。当一个段结束时，将当前覆盖的段的数量减一，并将该段添加到神奇的数据结构中。在每个事件之后，用当前覆盖的段数的值（它显示了与当前事件对应的点覆盖了多少段）加上上述数据结构返回的最大值（它显示了我们如何可以以最佳方式选择另一个点）。
如果这个数据结构可以执行所有给定的操作O(log n)，那么我们有一个O(n log n)解决方案（我们对事件进行排序，并对排序后的数组进行一次传递，为每个事件对此数据结构进行恒定数量的查询）。
那么我们如何实现这个数据结构呢？嗯，线段树在这里工作得很好。添加段就是向特定范围添加一个。删除一个段就是将特定范围内的所有元素减一。获取最大值只是线段树上的标准最大值操作。因此，我们需要一个支持两种操作的线段树：向范围添加一个常量并获取整个树的最大值。可以在O(log n)每次查询的时间。
还有一点需要注意：标准线段树要求坐标很小。我们可以假设它们永远不会超过2 * n（如果不是这种情况，我们可以压缩它们）。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
