题解 | 【模板】多重集合操作

from collections import defaultdict
from bisect import insort, bisect_left, bisect_right


class MultiSet:
    def __init__(self):
        self._set = defaultdict(int)
        self._vec = []
        self._size = 0

    def insert_value(self, x: int) -> None:
        """Insert a value into the multiset."""
        self._size += 1
        if self._set[x] == 0:
            insort(self._vec, x)
        self._set[x] += 1

    def erase_value(self, x: int) -> None:
        """Erase one occurrence of a value from the multiset."""
        if self._set[x] > 0:
            self._size -= 1
            self._set[x] -= 1
            if self._set[x] == 0:
                self._vec.pop(bisect_left(self._vec, x))

    def count(self, x: int) -> int:
        """Return the count of x in the multiset."""
        return self._set[x]

    def size(self) -> int:
        """Return the total size of the multiset."""
        return self._size

    def get_predecessor(self, x: int) -> int:
        """Return the predecessor of x or -1 if none exists."""
        index = bisect_left(self._vec, x)
        return -1 if index == 0 else self._vec[index - 1]

    def get_successor(self, x: int) -> int:
        """Return the successor of x or -1 if none exists."""
        index = bisect_right(self._vec, x)
        return -1 if index == len(self._vec) else self._vec[index]


def main():
    multiset = MultiSet()
    q = int(input())
    for _ in range(q):
        line = map(int, input().split())
        cnt, op, x = 0, 0, 0
        for i in line:
            if cnt == 0:
                op = i
            else: 
                x = i
            cnt += 1
        
        if op == 1:
            multiset.insert_value(x)
        elif op == 2:
            multiset.erase_value(x)
        elif op == 3:
            print(multiset.count(x))
        elif op == 4:
            print(multiset.size())
        elif op == 5:
            print(multiset.get_predecessor(x))
        elif op == 6:
            print(multiset.get_successor(x))


if __name__ == "__main__":
    main()