点和细分

Question

我正在做在线课程并且遇到了这个问题.

第一行包含两个非负整数1≤n,m≤50000 - 一行中的段数和点数.接下来的n行包含两个整数a_i≤b_i,用于定义第i个段.下一行包含定义点的m个整数.所有整数的绝对值最多为10 ^ 8.对于每个段,从n-points表输出它使用的点数.

我的解决方案是:

for point in points:
    occurrence = 0
    for l, r in segments:
        if l <= point <= r:
           occurrence += 1
    print(occurrence),

该算法的复杂性为O(m*n),显然效率不高.解决这个问题的最佳方法是什么？任何帮助将不胜感激!

样本输入:

2 3
0 5
7 10
1 6 11

样本输出:

1 0 0

样本输入2:

1 3
-10 10
-100 100 0

样本输出2:

0 0 1

Answer 1

您可以使用扫描线算法来解决此问题.

首先,将每个细分分为两个点,即开放点和关闭点.

将所有这些点与这些点一起添加m,并根据它们的位置对它们进行排序.

迭代点列表,维护a counter,每次遇到开放点时,增加counter,如果遇到终点,则减少它.如果在列表m点中遇到一个点,则此点的结果是此时的值counter.

For example 2, we have:

1 3
-10 10
-100 100 0

After sorting, what we have is:

-100 -10 0 10 100

At point -100, we have `counter = 0`

At point -10, this is open point, we increase `counter = 1`

At point 0, so result is 1

At point 10, this is close point, we decrease `counter = 0`

At point 100, result is 0

So, result for point -100 is 0, point 100 is 0 and point 0 is 1 as expected.

时间复杂度为O((n + m)log(n + m)).