ABC330 E — Mex and Update

1# -*- coding: utf-8 -*-2 3 4# See:5# https://atcoder.jp/contests/abc194/submissions/207020496class BITSet:7    """8    set[i] : 集合のi番目に小さい要素を取得 O(logN)9    len(set) : 要素数 O(1)10    set.add(x) : xを追加 O(logN)11    set.remove(x) : xを削除 O(logN)12    set.mex() : 集合にない最小の非負整数を取得 O(logN)13    """14 15    def __init__(self, max_value: int) -> None:16        self.max_value: int = max_value + 117        self.bit = BIT(self.max_value)18        self.contain: list[int] = [0] * self.max_value19        self.size: int = 020 21    def __getitem__(self, key):22        return self.bit.bisect_left(key)23 24    def __len__(self) -> int:25        return self.size26 27    def add(self, key) -> None:28        if not self.contain[key]:29            self.size += 130            self.contain[key] = 131            self.bit.add(key)32 33    def remove(self, key) -> None:34        if self.contain[key]:35            self.size -= 136            self.contain[key] = 037            self.bit.add(key, -1)38 39    def mex(self) -> int:40        result = 041        value = k = self.bit.max_bit42 43        while k:44            key = result + k45 46            if key <= self.max_value and self.bit.data[key] == k:47                value -= k48                result += k49 50            k >>= 151 52        return result53 54 55class BIT:56    """57    bit.add(i, val) : s[i] += val O(logN)58    bit.sum(l, r) : s[l:r+1]の区間和、r指定なしのときs[:l]の区間和 O(logN)59    bit.bisect(val) : s[:i+1] >= valとなる最小のi O(logN)60    """61 62    def __init__(self, size: int) -> None:63        self.size: int = size + 164        self.data: list[int] = [0] * self.size65        self.max_bit: int = 1 << self.size.bit_length() - 166 67    def add(self, key, value=1) -> None:68        key += 169 70        while key < self.size:71            self.data[key] += value72            key += key & -key73 74    def sum(self, left, right=None) -> int:75        left_result = 076 77        while left:78            left_result += self.data[left]79            left -= left & -left80 81        if right is None:82            return left_result83 84        right += 185        right_result = 086 87        while right:88            right_result += self.data[right]89            right -= right & -right90 91        return right_result - left_result92 93    def bisect_left(self, value) -> int:94        result = 095        k = self.max_bit96 97        while k:98            key = result + k99 100            if key < self.size and self.data[key] < value:101                value -= self.data[key]102                result += k103 104            k >>= 1105 106        return result107 108 109def main():110    import sys111    from collections import defaultdict112 113    input = sys.stdin.readline114 115    n, q = map(int, input().split())116    a = list(map(int, input().split()))117    b = BITSet(n + 1)118    d = defaultdict(int)119 120    for ai in a:121        d[min(ai, n + 1)] += 1122 123    for key in d.keys():124        b.add(key)125 126    for _ in range(q):127        i, xi = map(int, input().split())128        i -= 1129        xi = min(xi, n + 1)130 131        d[a[i]] -= 1132 133        if d[a[i]] == 0:134            b.remove(a[i])135 136        a[i] = xi137        d[xi] += 1138 139        if d[xi] == 1:140            b.add(xi)141 142        print(b.mex())143 144 145if __name__ == "__main__":146    main()147