順序付き多重集合 (Binary Indexed Tree)
(DataStructure/SortedSet/SortedMultiSetBIT.py)

• View this file on GitHub
• Last update: 2021-02-06 18:04:37+09:00

概要

Binary Indexed Tree による順序付き多重集合。集合に属する可能性のある要素を、あらかじめ与える必要があることに注意。

使い方

SortedMultiSetBIT(cands: Iterable[int])
cands 内の要素を元として含むことが可能な、空の順序付き多重集合を作成する。n = len(cands) とすると、計算量 $O(n \log n)$

• __contains__(val: int) -> bool
  要素 val が集合に属しているかどうかを返す。計算量 $O(\log n)$

• __len__() -> int
  集合の大きさを返す。計算量 $O(1)$

• add(val: int) -> bool
  要素 val を集合に追加し、True を返す。val が cands の要素ではない場合は例外 KeyError が発生するので注意。計算量 $O(\log n)$

• remove(val: int) -> bool
  集合から val を 1 つだけ削除する。削除に成功した場合は True を、失敗した場合 (val が集合に属していなかった場合) は False を返す。計算量 $O(\log n)$

• all_remove(val: int) -> bool
  集合から val を全て削除する。削除に成功した場合は True を、失敗した場合 (val が集合に属していなかった場合) は False を返す。計算量 $O(\log n)$

• count(vl: int, vr: int) -> int
  集合内の vl 以上かつ vr 未満である要素の数を返す。計算量 $O(\log n)$

• kth_smallest(k: int) -> int
  集合内で k 番目 (0-indexed) に小さい要素を返す。計算量 $O(\log n)$

• kth_largest(k: int) -> int
  集合内で k 番目 (0-indexed) に大きい要素を返す。計算量 $O(\log n)$

• prev_val(upper: int) -> int
  集合内で upper よりも小さい最大の要素を返す。そのような要素が存在しない場合は None を返す。計算量 $O(\log n)$

• next_val(lower: int) -> int
  集合内で lower 以上の最小の要素を返す。そのような要素が存在しない場合は None を返す。計算量 $O(\log n)$

• all_dump() -> List[Tuple[int, int]]
  集合内の全ての (要素, 個数) の組を、要素の小さい順に返す。計算量 $O(n)$

Depends on

• 順序付き集合 (Binary Indexed Tree) (DataStructure/SortedSet/SortedSetBIT.py)

Verified with

• TestCase/yukicoder/yuki0649.SortedMultiSetBIT.test.py
• TestCase/yukicoder/yuki1110.SortedMultiSetBIT.test.py

Code

from DataStructure.SortedSet.SortedSetBIT import SortedSetBIT


class SortedMultiSetBIT(SortedSetBIT):
    def __init__(self, cands):
        super().__init__(cands)

    def add(self, val):
        i = self.comp[val] + 1
        while i <= self.size:
            self.bit[i] += 1
            i += i & -i
        self.cnt += 1
        return True

    def all_remove(self, val):
        if val not in self:
            return False
        i = self.comp[val] + 1
        cnt = self._count(i) - self._count(i - 1)
        while i <= self.size:
            self.bit[i] -= cnt
            i += i & -i
        self.cnt -= cnt
        return True

    def all_dump(self):
        res = self.bit[:]
        for i in reversed(range(1, self.size)):
            if i + (i & -i) > self.size:
                continue
            res[i + (i & -i)] -= res[i]
        return [(self.array[i], cnt) for i, cnt in enumerate(res[1:]) if cnt]

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page