Atcoderの2023年8月の言語アップデートに伴い、Pythonでsortedcontainersライブラリが使えるようになりました。平衡二分木を使ったMultiSetはPythonにないので、今後はsortedcontainersのSortedListが使えそうです。
SortedListのメソッド一覧と計算量
Grant Jenksの公式ドキュメントを参照しました。
| メソッド | 説明 | 計算量 |
|---|---|---|
add(value) |
要素をソートして追加 | $O(\log n)$ |
update(iterable) |
複数の要素をソートして追加 | $O(k \log n)$ |
clear() |
すべての要素を削除 | $O(n)$ |
discard(value) |
要素を削除（存在しない場合は何もしない） | $O(\log n)$ |
remove(value) |
要素を削除（存在しない場合はValueError） | $O(\log n)$ |
pop(index=-1) |
指定されたインデックスの要素を削除して返す | $O(\log n)$ |
bisect_left(value) |
二分探索で挿入位置を左側から探す | $O(\log n)$ |
bisect_right(value) |
二分探索で挿入位置を右側から探す | $O(\log n)$ |
count(value) |
指定された値の出現回数を取得 | $O(\log n)$ |
index(value, start=0, stop=None) |
指定された値のインデックスを取得（存在しない場合はValueError） | $O(\log n)$ |
__getitem__(index) |
指定されたインデックスの要素を取得。スライスもサポート。 | $O(\log n)$ |
使用例
from sortedcontainers import SortedList
# SortedListのインスタンスを作成
sl = SortedList([3, 1, 4, 1, 5, 9, 2, 6, 5])
print(f"Initial list: {sl}") # [1, 1, 2, 3, 4, 5, 5, 6, 9]
# add(value): 要素をソートして追加
sl.add(8)
print(f"Added 8: {sl}") # [1, 1, 2, 3, 4, 5, 5, 6, 8, 9]
# update(iterable): 複数の要素をソートして追加
sl.update([7, 10])
print(f"Updated with [7, 10]: {sl}") # [1, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 10]
# clear(): すべての要素を削除
sl.clear()
print(f"Cleared list: {sl}") # []
# 以下の操作は新たなSortedListで行う
sl = SortedList([1, 2, 3, 4, 5])
# discard(value): 要素を削除（存在しない場合は何もしない）
sl.discard(10)
print(f"Discarded 10 (not in list): {sl}") # [1, 2, 3, 4, 5]
# remove(value): 要素を削除（存在しない場合はValueError）
sl.remove(1)
print(f"Removed 1: {sl}") # [2, 3, 4, 5]
# pop(index=-1): 指定されたインデックスの要素を削除して返す
pop_val = sl.pop(-1)
print(f"Popped last element ({pop_val}): {sl}") # [2, 3, 4]
# bisect_left(value): 二分探索で挿入位置を左側から探す
print(f"Bisect left of 2: {sl.bisect_left(2)}") # 0
# bisect_right(value): 二分探索で挿入位置を右側から探す
print(f"Bisect right of 2: {sl.bisect_right(2)}") # 1
# count(value): 指定された値の出現回数を取得
print(f"Count of 2: {sl.count(2)}") # 1
# index(value, start=0, stop=None): 指定された値のインデックスを取得（存在しない場合はValueError）
print(f"Index of 2: {sl.index(2)}") # 0
# __getitem__(index): 指定されたインデックスの要素を取得
print(f"Element at index 1: {sl[1]}") # 3