ABC294 D — Bank

1# -*- coding: utf-8 -*-2 3 4import math5from bisect import bisect_left, bisect_right6from typing import Generic, Iterable, Iterator, TypeVar, Union, List7 8T = TypeVar('T')9 10 11class SortedSet(Generic[T]):12    """Sorted set (set) in C++.13    See:14    https://qiita.com/tatyam/items/492c70ac4c955c05560215    https://github.com/tatyam-prime/SortedSet/blob/main/SortedSet.py16    """17 18    BUCKET_RATIO = 5019    REBUILD_RATIO = 17020 21    def _build(self, a=None) -> None:22        "Evenly divide `a` into buckets."23        if a is None:24            a = list(self)25 26        size = self.size = len(a)27        bucket_size = int(math.ceil(math.sqrt(size / self.BUCKET_RATIO)))28        self.a = [a[size * i // bucket_size: size * (i + 1) // bucket_size] for i in range(bucket_size)]29 30    def __init__(self, a: Iterable[T] = []) -> None:31        """Make a new SortedSet from iterable.32            / O(N) if sorted and unique / O(N log N)33        """34        a = list(a)35 36        if not all(a[i] < a[i + 1] for i in range(len(a) - 1)):   # type: ignore37            a = sorted(set(a))  # type: ignore38 39        self._build(a)40 41    def __iter__(self) -> Iterator[T]:42        for i in self.a:43            for j in i:44                yield j  # type: ignore45 46    def __reversed__(self) -> Iterator[T]:47        for i in reversed(self.a):48            for j in reversed(i):49                yield j50 51    def __len__(self) -> int:52        return self.size53 54    def __repr__(self) -> str:55        return "SortedSet" + str(self.a)56 57    def __str__(self) -> str:58        s = str(list(self))59        return "{" + s[1: len(s) - 1] + "}"60 61    def _find_bucket(self, x: T) -> List[T]:62        "Find the bucket which should contain x. self must not be empty."63        for a in self.a:64            if x <= a[-1]:   # type: ignore65                return a66        return a67 68    def __contains__(self, x: T) -> bool:69        if self.size == 0:70            return False71 72        a = self._find_bucket(x)73        i = bisect_left(a, x)  # type: ignore74 75        return i != len(a) and a[i] == x76 77    def add(self, x: T) -> bool:78        "Add an element and return True if added. / O(√N)"79        if self.size == 0:80            self.a = [[x]]81            self.size = 182            return True83 84        a = self._find_bucket(x)85        i = bisect_left(a, x)  # type: ignore86 87        if i != len(a) and a[i] == x:88            return False89 90        a.insert(i, x)91        self.size += 192 93        if len(a) > len(self.a) * self.REBUILD_RATIO:94            self._build()95 96        return True97 98    def discard(self, x: T) -> bool:99        "Remove an element and return True if removed. / O(√N)"100        if self.size == 0:101            return False102 103        a = self._find_bucket(x)104        i = bisect_left(a, x)  # type: ignore105 106        if i == len(a) or a[i] != x:107            return False108 109        a.pop(i)110        self.size -= 1111 112        if len(a) == 0:113            self._build()114        return True115 116    def lt(self, x: T) -> Union[T, None]:117        "Find the largest element < x, or None if it doesn't exist."118        for a in reversed(self.a):119            if a[0] < x:  # type: ignore120                return a[bisect_left(a, x) - 1]  # type: ignore121        return None122 123    def le(self, x: T) -> Union[T, None]:124        "Find the largest element <= x, or None if it doesn't exist."125        for a in reversed(self.a):126            if a[0] <= x:  # type: ignore127                return a[bisect_right(a, x) - 1]  # type: ignore128        return None129 130    def gt(self, x: T) -> Union[T, None]:131        "Find the smallest element > x, or None if it doesn't exist."132        for a in self.a:133            if a[-1] > x:  # type: ignore134                return a[bisect_right(a, x)]  # type: ignore135        return None136 137    def ge(self, x: T) -> Union[T, None]:138        "Find the smallest element >= x, or None if it doesn't exist."139        for a in self.a:140            if a[-1] >= x:   # type: ignore141                return a[bisect_left(a, x)]  # type: ignore142        return None143 144    def __getitem__(self, x: int) -> T:145        "Return the x-th element, or IndexError if it doesn't exist."146        if x < 0:147            x += self.size148        if x < 0:149            raise IndexError150 151        for a in self.a:152            if x < len(a):153                return a[x]  # type: ignore154 155            x -= len(a)156        raise IndexError157 158    def index(self, x: T) -> int:159        "Count the number of elements < x."160        ans = 0161 162        for a in self.a:163            if a[-1] >= x:  # type: ignore164                return ans + bisect_left(a, x)  # type: ignore165            ans += len(a)166        return ans167 168    def index_right(self, x: T) -> int:169        "Count the number of elements <= x."170        ans = 0171 172        for a in self.a:173            if a[-1] > x:  # type: ignore174                return ans + bisect_right(a, x)  # type: ignore175            ans += len(a)176        return ans177 178 179def main():180    from collections import deque181    import sys182 183    input = sys.stdin.readline184 185    n, q = map(int, input().split())186    d = deque([i for i in range(1, n + 1)])187    s = SortedSet()188    ans = list()189 190    for _ in range(q):191        qi = list(map(int, input().split()))192 193        if qi[0] == 1:194            di = d.popleft()195            s.add(di)196        elif qi[0] == 2:197            s.discard(qi[1])198        else:199            ans.append(s[0])200    201    print(*ans, sep="\n")202    203 204if __name__ == "__main__":205    main()206