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

Answer 1

lens 的数据结构类似于多重集，也可用作 Counter。就时间复杂度而言，算法的瓶颈部分是：

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

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

为了改进这部分算法，我建议使用堆。 heapq 提供了最小堆实现。因为你实际上需要一个最大堆，所以你只需用 negative 长度喂它。

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

Python 中的多重集

Multisets in Python

python

algorithm

set

bigdata

data-structures

Input

Output

Constraints

Example