python - Python 中的多重集

Question

我正在 CSES 上解决这个问题， Traffic Lights :

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

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

Input

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

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

Output

Print the length of the longest passage without traffic lights aftereach 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++中有一种数据结构叫做多集。但是在python中找不到类似的数据结构。任何帮助表示赞赏。

Answer 1

lens 的数据结构就像一个多重集，也可以用作 Counter。就时间复杂度而言，算法的瓶颈部分是:

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

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

为了改进这部分算法，我建议使用堆。 heapq 提供了最小堆实现。由于您实际上需要一个最大堆，因此您只需为其提供负长度。

其次，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 = " ")