SortedList

2022年7月18日

説明

Python で書かれた要素を追加・削除しても整列状態を保てる List のようなもの。SortedList に格納する値は comparable でなければならない。タプルやリストも格納可能。Python Sorted Containers

使い方

ソースコードを .py ファイルの先頭に貼り付けて使う。

操作	メソッド	計算量
要素の追加	add(value)	$ \small O(\log N) $
要素の削除	discard(value), remove(value)	$ \small O(\log N) $
要素の検索	bisect_left(value), bisect_right(value)	$ \small O(\log N) $

remove は value が存在していないと ValueError になるが、discard は value が存在していなくてもエラーにはならない

コード例 (ABC260 D)

def solve(n,k,p):
    sl = SortedList()
    yama = defaultdict(list)
    eat = [-1 for _ in range(n)]
    for i in range(n):
        pi = p[i]
        idx = sl.bisect_left(pi)
        if idx < len(sl):
            key = sl[idx]
            sl.remove(key)
            yama[pi] = yama.pop(key)
        yama[pi].append(pi)

        if len(yama[pi]) < k:
            sl.add(pi)
        else:
            for card in yama[pi]:
                eat[card-1] = i+1
    return eat