P16458 [UOI 2026] mex plus

对于每一对数，你需要从中选一个数放入数组 $A$，另一个数放入数组 $B$。也就是说，对于每一对 $(x, y)$，可以进行以下两种选择之一： - 将 $x$ 加入数组 $A$，将 $y$ 加入数组 $B$； - 将 $y$ 加入数组 $A$，将 $x$ 加入数组 $B$。 当所有数对的选择都完成后，数组 $A$ 和数组 $B$ 的长度将相等。 对于一个数组 $C$，记 $\operatorname{mex}(C)$ 表示没有在数组 $C$ 中出现的最小非负整数。例如，若 $ C = [0, 1, 4, 1, 2], $ 则 $\operatorname{mex}(C) = 3$，因为数字 $0$、$1$ 和 $2$ 在数组中出现了，而数字 $3$ 没有。若 $ C = [1, 2, 3], $ 则 $\operatorname{mex}(C) = 0$，因为数字 $0$ 没有在数组中出现。 你需要最大化 $ \operatorname{mex}(A) + \operatorname{mex}(B). $ 在初始的数对集合之后，会给出 $q$ 个询问。每个询问要么向集合中添加一个数对，要么从集合中删除一个数对。在每次询问之后，你需要针对当前的数对集合，重新求出 $ \operatorname{mex}(A) + \operatorname{mex}(B) $ 的最大可能值。 重要的是，在每次询问之后，你可以重新选择所有数对中数字的分配方式。也就是说，之前的选择不会限制后续的答案。

第一行包含两个整数 $n$ 和 $q$ $(1 \le n \le 2 \cdot 10^5, 0 \le q \le 2 \cdot 10^5)$ —— 初始的数对个数以及询问的个数。 接下来的 $n$ 行给出初始的数对。 其中第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ $(0 \le a_i \le b_i \le 10^9)$。 再接下来的 $q$ 行给出询问。每个询问为以下两种格式之一： $ \texttt{+ } x \ y $ 或 $ \texttt{- } x \ y, $ 其中 $0 \le x \le y \le 10^9$。 查询 $\texttt{+ x y}$ 意味着将数对 $(x, y)$ 添加到集合中。 查询 $\texttt{- x y}$ 意味着从集合中删除一个数对 $(x, y)$。保证在执行这样的查询时，集合中至少存在一个这样的数对。

输出 $q + 1$ 个整数。 第一个整数是对于初始的数对集合，$ \operatorname{mex}(A) + \operatorname{mex}(B) $ 的最大值。 然后，在每次询问之后，输出对于当前数对集合，$ \operatorname{mex}(A) + \operatorname{mex}(B) $ 的最大值。 每个答案输出在单独的一行中。

在第一个例子中，对于初始的数对集合，最优的选择例如是 $A = [0, 2, 1, 4, 3]$，$B = [1, 0, 1, 5, 2]$。此时 $\operatorname{mex}(A) = 5$，$\operatorname{mex}(B) = 3$，总和为 $8$。在添加数对 $(4, 5)$ 之后，可以选择例如 $A = [0, 2, 1, 5, 3, 4]$，$B = [1, 0, 1, 4, 2, 5]$，此时 $\operatorname{mex}(A) = 6$，$\operatorname{mex}(B) = 3$，总和为 $9$。 在第二个例子中，值的多重集为 $\{0, 0, 1, 1, 1, 1, 1, 1, 1, 1\}$。 最优的选择例如是 $A = [1, 1, 1, 1, 0]$，$B = [1, 1, 1, 1, 0]$。此时 $\operatorname{mex}(A) = \operatorname{mex}(B) = 2$，总和为 $4$。 在第三个例子中，没有一个值等于 $0$，因此无论如何选择，都无法使 $0 \in A$ 或 $0 \in B$。因此 $\operatorname{mex}(A) = \operatorname{mex}(B) = 0$，总和为 $0$。 在第四个例子中，最优的选择例如是 $A = [2, 3, 0, 3, 10]$，$B = [2, 3, 1, 4, 0]$。此时 $\operatorname{mex}(A) = 1$，$\operatorname{mex}(B) = 5$，总和为 $6$。 在第五个例子中，最优的选择例如是 $A = [3, 4, 9, 0, 6]$，$B = [1, 5, 0, 0, 5]$。此时 $\operatorname{mex}(A) = 1$，$\operatorname{mex}(B) = 2$，总和为 $3$。 ### 计分 - （$2$ 分）：$n \le 20$，$q = 0$； - （$7$ 分）：对于所有初始数对满足 $b_i = 10^9$，且对于所有询问满足 $y = 10^9$； - （$8$ 分）：对于所有初始数对满足 $a_i = 0$，且对于所有询问满足 $x = 0$； - （$9$ 分）：$n \le 500$，$q \le 500$； - （$11$ 分）：$q = 0$； - （$10$ 分）：所有询问均为 $\texttt{+ x y}$ 形式； - （$9$ 分）：所有询问均为 $\texttt{- x y}$ 形式； - （$13$ 分）：在任意时刻，对于当前集合中的任意三个数对，若第一个数对与第二个数对共享一个数字，且第二个数对与第三个数对共享一个数字，则存在一个数字同时属于这三个数对； - （$20$ 分）：$n, q \le 10^5$； - （$11$ 分）：无额外限制。 翻译由 DeepSeek V4 Pro 完成