感人的片段 [英] Touching segments

问题描述

任何人都可以请建议我的算法这一点。

正在给定的开始和N片段的结束点在x轴。 有多少这些段可触及，甚至在其边缘，正好两条线垂直于它们？

采样输入：

  3
五
2 3
1 3
1 5
3 4
4 5
五
1 2
1 3
2 3
1 4
1 5
3
1 2
3 4
5 6
 

示例输出：

 案例1：5
案例2：5
案例3：2
 

说明：

• 案例1：我们将借助两条线（平行于Y轴）交叉的X轴的点2和4。这两条线将涉及所有五个部分
• 案例2：我们可以在2触碰所有的点，即使穿越X轴一行
• 在案例三：这是不可能在这种情况下，触摸两点多

约束：

  1≤N≤10 ^ 5
0≤A＆LT; b≤10 ^ 9
 

解决方案

让我们假设我们有一个数据结构，有效地支持了以下操作：

1. 添加一个片段。

2. 删除片段。

3. 返回覆盖一个点段（也就是最好的点）。

的最大数量

如果有这样的结构，我们可以得到以下面的方式有效地使用最初的问题：

1. 让我们创建活动的数组（一个事件，每一段的开始和一个用于结束），并作为排序依据的x坐标。

2. 添加全部段神奇的数据结构。

3. 遍历所有事件，并执行以下操作：当一个段开始，添加一个到目前涵盖的段数，并从数据结构中删除。当一个段结束时，从目前涵盖段的数目减一，这段添加到神奇数据结构。每个事件后，更新具有当前包括的段数的值的答案（它显示有多少个段覆盖其对应于当前事件的点），加上由上述的数据结构中返回最大值（它显示了如何我们可以选择在尽可能最好的方式还有一点）。

如果这个数据结构，可以在 0执行所有给定的操作（log n）的，然后我们有一个为O（n log n）的溶液（我们的事件排序并进行一次传过来的有序数组进行查询的恒定数量来该数据结构为每个事件）。

那么怎样才能实现这个数据结构？好了，段树正常工作在这里。增加一个段加一特定的范围。卸下段是减1在特定范围内的所有元素。获取婷最大的是刚上段树标准最大运行。因此，我们需要一个支持两个操作段树：添加一个常数范围，并得到最大限度的为整个树。它可以在每次查询O（log n）的的时间内完成。

还要说明一点：一个标准的段树需要的坐标很小。我们可以假设，他们从来没有超过 2 * N （如果不是这样，我们可以COM preSS它们）。

Can anyone please suggest me algorithm for this.

You are given starting and the ending points of N segments over the x-axis. How many of these segments can be touched, even on their edges, by exactly two lines perpendicular to them?

Sample Input :

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

Sample Output :

Case 1: 5
Case 2: 5
Case 3: 2

Explanation :

• Case 1: We will draw two lines (parallel to Y-axis) crossing X-axis at point 2 and 4. These two lines will touch all the five segments.
• Case 2: We can touch all the points even with one line crossing X-axis at 2.
• Case 3: It is not possible to touch more than two points in this case.

Constraints:

1 ≤ N ≤ 10^5
0 ≤ a < b ≤ 10^9

解决方案

Let assume that we have a data structure that supports the following operations efficiently:

1. Add a segment.

2. Delete a segment.

3. Return the maximum number of segments that cover one point(that is, the "best" point).

If have such a structure, we can get use the initial problem efficiently in the following manner:

1. Let's create an array of events(one event for the start of each segment and one for the end) and sort by the x-coordinate.

2. Add all segments to the magical data structure.

3. Iterate over all events and do the following: when a segment start, add one to the number of currently covered segments and remove it from that data structure. When a segment ends, subtract one from the number of currently covered segment and add this segment to the magical data structure. After each event, update the answer with the value of the number of currently covered segments(it shows how many segments are covered by the point which corresponds to the current event) plus the maximum returned by the data structure described above(it shows how we can choose another point in the best possible way).

If this data structure can perform all given operations in O(log n), then we have an O(n log n) solution(we sort the events and make one pass over the sorted array making a constant number of queries to this data structure for each event).

So how can we implement this data structure? Well, a segment tree works fine here. Adding a segment is adding one to a specific range. Removing a segment is subtracting one from all elements in a specific range. Get ting the maximum is just a standard maximum operation on a segment tree. So we need a segment tree that supports two operations: add a constant to a range and get maximum for the entire tree. It can be done in O(log n) time per query.

One more note: a standard segment tree requires coordinates to be small. We may assume that they never exceed 2 * n(if it is not the case, we can compress them).

这篇关于感人的片段的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！