P13610 [NWRRC 2022] Mex and Cards

Mike 喜欢玩纸牌。他的牌堆中每张牌上都写有一个从 $0$ 到 $n-1$ 的整数。最初，牌堆中有 $a_i$ 张牌的点数为 $i$。 今天 Mike 正在学习 $\textit{mex}$ 的概念。一个整数集合的 mex 是集合中不存在的最小非负整数。例如，$\operatorname{mex}(\{4, 1, 4, 12, 0, 7, 0, 0, 5\}) = 2$。 Mike 会把所有的牌分成若干个非空的牌堆。每张牌必须且只能属于一个牌堆。然后他会计算每个牌堆中所有牌的点数的 mex，并将所有牌堆的 mex 求和。Mike 想要找到一种分堆方式，使得这些 mex 之和最大。 此外，牌堆还会发生 $q$ 次修改：有时会往牌堆中加入一张新牌，有时会从牌堆中移除一张牌。Mike 想要在每次修改后（包括最初未修改时）都找到一种分堆方式，使得 mex 之和最大。 请你在每次修改后（包括最初未修改时）输出最大可能的 mex 之和。

第一行包含一个整数 $n$，表示牌的点数范围（$1 \le n \le 2 \cdot 10^5$）。 第二行包含 $n$ 个整数 $a_0, a_1, \ldots, a_{n-1}$，表示初始时点数为 $0, 1, \ldots, n-1$ 的牌的数量（$0 \le a_i \le 10^6$）。 第三行包含一个整数 $q$，表示牌堆的修改次数（$0 \le q \le 2 \cdot 10^5$）。 接下来的 $q$ 行，每行包含两个整数 $p_i$ 和 $v_i$，描述第 $i$ 次修改（$1 \le p_i \le 2$；$0 \le v_i < n$）。如果 $p_i = 1$，表示加入一张点数为 $v_i$ 的新牌；如果 $p_i = 2$，表示移除一张点数为 $v_i$ 的牌。 保证对于每次 $p_i = 2$ 的操作，操作前牌堆中至少有一张点数为 $v_i$ 的牌。

输出 $q+1$ 个整数，依次表示初始状态和每次修改后，所有牌分堆后最大可能的 mex 之和。

对于示例测试的初始牌堆，一种最优分堆方式是：将点数为 $0$ 和 $2$ 的牌分为一堆，将点数为 $0, 1, 2, 2, 4$ 的牌分为另一堆，将点数为 $4$ 的牌单独分为一堆。此时各堆的 mex 分别为 $\operatorname{mex}(\{0, 2\}) + \operatorname{mex}(\{0, 1, 2, 2, 4\}) + \operatorname{mex}(\{4\}) = 1 + 3 + 0 = 4$。 由 ChatGPT 4.1 翻译