Python中的多重集合

Question

我正在解决CSES上的这个问题， 交通信号灯:

There is a street of length whose positions are numbered 0,1,…,. Initially there are no traffic lights, but sets of traffic lights are added to the street one after another.

Your task is to calculate the length of the longest passage without traffic lights after each addition.

Input

The first input line contains two integers and : the length of the street and the number of sets of traffic lights.

Then, the next line contains n integers ₁,₂,…,: the position of each set of traffic lights. Each position is distinct.

Output

Print the length of the longest passage without traffic lights after each addition.

Constraints

• 1 ≤ ≤ 10⁹
• 1 ≤ ≤ 2⋅10⁵
• 0 < <

Example

Input:

8 3
3 6 2

Output:

5 3 3

要有效地解决像这样的问题，我需要在Python中使用类似于列表的数据结构，但是元素的搜索和删除需要是O(1)，或者类似于集合的数据结构，但我需要能够插入多个相同的元素并保留顺序。

我的代码如下：

from collections import defaultdict
from bisect import bisect_right , insort
x , n = list(map(int  , input().split()))
arr = list(map(int , input().split()))
lens = defaultdict(int)
lens[x] = 1
lights = [0,x]
for ele in arr:
    idx = bisect_right(lights , ele)
    to_be_removed = lights[idx] - lights[idx-1]
    lens[to_be_removed] -= 1
    lens[lights[idx]-ele] += 1
    lens[ele-lights[idx-1]] += 1
    insort(lights , ele)
    print(max([x for x in lens.keys() if lens[x]])  , end =" ") 

然而，这段代码运行速度较慢。C++中有一种称为multi-sets的数据结构，但是在Python中找不到类似的数据结构。欢迎任何帮助。

- eyah

---

你可以看一下 collections.Counter。 - hilberts_drinking_problem

特别是计数器保持非负。 - greybeard

insort(lights, ele) 是一个 O(n) 操作。列表中的 max 也是 O(n) 操作。因此，总体复杂度仍然为 O(n^2)。您可以通过维护先前的最大值并基于新部分将插入到哪里来更新最大值部分。您需要搜索和插入都是 log(n) - 因此，您需要 BST/AVL/RB 树来优化，以使整体复杂度为 Onlog(n)，您可以使用 https://pypi.python.org/pypi/bintrees/ - Jay

Answer 1

你的 `lens` 数据结构类似于一个多重集合，也可以用 `Counter` 来表示。在时间复杂度方面成为瓶颈的部分算法是这个：

max([x for x in lens.keys() if lens[x]]) 

这是一个具有线性时间复杂度的操作，因此它将使算法呈二次方增长。

为了改进算法的这一部分，我建议使用堆。有 heapq 提供了 min 堆实现。由于实际需要的是 max 堆，所以只需提供负数长度即可。

其次，insort 也具有线性时间复杂度（虽然比上面的max()表达式使用更少的时间）。你可以通过使用自平衡搜索树实现来改进它，没有标准库提供，但是有提供排序列表的库，如sortedcontainers。

以下是如何调整代码以实现这两个想法：

from collections import defaultdict
from heapq import heappush, heappop
from sortedcontainers import SortedList

x , n = list(map(int  , input().split()))
arr = list(map(int , input().split()))

lens = defaultdict(int)
lens[x] = 1
lights = SortedList([0, x])  # For faster insertion
heap = [-x]  # Put total width also in a heap
for ele in arr:
    idx = lights.bisect_right(ele)
    to_be_removed = lights[idx] - lights[idx-1]
    lens[to_be_removed] -= 1

    # Add widths to the heap when they are the only occurrences
    right = lights[idx]-ele
    if lens[right] == 0:
        heappush(heap, -right)
    lens[right] += 1

    left = ele-lights[idx-1]
    if lens[left] == 0:
        heappush(heap, -left)
    lens[left] += 1

    # Remove the largest width as long as it no longer represents a segment
    while lens[-heap[0]] == 0:
        heappop(heap)
    
    # The add method is O(logn)
    lights.add(ele)
    # Just output the largest width in the heap
    print(-heap[0], end = " ")

- trincot

---

我们这里真的需要一个 heapq 吗？我们只需保留 current_max（以及相应的索引），并查看新插入索引的左侧/右侧，以确定是否需要更新 current_max。 - Jay

很难保持当前的最大值，因为当当前的最大值被删除时，你不知道下一个最大值是什么。这就是堆的作用所在。 - trincot

当新索引位于current_max区间内时，current_max将会减少，因此我们需要一个堆。 - Jay

很遗憾，由于排序容器是第三方库，无法在解决方案中使用。@trincot - eyah

还有，为什么我们在这里使用lights.add()，当我们已经知道要插入元素的位置？ - eyah

@eyah，insort需要移动插入点之后的所有值。这就是O(n)时间复杂度的部分。某种平衡树实现将解决这个问题，并使其变为O(logn)。排序容器的源代码在github上。它们使用一种列表的B树组织方式。由于没有类似的标准库，因此要么使用第三方库，要么实现自己的平衡搜索树解决方案。你还有什么问题需要我回答？ - trincot