P16458 [UOI 2026] mex plus

From each pair, you need to choose one number for array $A$ and the other number for array $B$. That is, for each pair $(x, y)$, one of the following two choices can be made: - add $x$ to array $A$ and $y$ to array $B$; - add $y$ to array $A$ and $x$ to array $B$. After choices are made for all pairs, arrays $A$ and $B$ will have the same length. For an array $C$, let $\operatorname{mex}(C)$ denote the smallest non-negative integer that does not appear in array $C$. For example, if $ C = [0, 1, 4, 1, 2], $ then $\operatorname{mex}(C) = 3$, because numbers $0$, $1$, and $2$ appear in the array, while number $3$ does not. If $ C = [1, 2, 3], $ then $\operatorname{mex}(C) = 0$, because number $0$ does not appear in the array. You need to maximize $ \operatorname{mex}(A) + \operatorname{mex}(B). $ After the initial set of pairs, $q$ queries are given. Each query either adds one pair to the set or removes one pair from the set. After each query, you need to find again the maximum possible value of $ \operatorname{mex}(A) + \operatorname{mex}(B) $ for the current set of pairs. It is important that after each query, you may choose the order of numbers in all pairs again. That is, the previous choice does not restrict the next answers.

The first line contains two integers $n$ and $q$ $(1 \le n \le 2 \cdot 10^5, 0 \le q \le 2 \cdot 10^5)$ --- the initial number of pairs and the number of queries. The next $n$ lines contain the initial pairs. The $i$-th of these lines contains two integers $a_i$ and $b_i$ $(0 \le a_i \le b_i \le 10^9)$. The next $q$ lines contain the queries. Each query has one of the following formats: $ \texttt{+ } x \ y $ or $ \texttt{- } x \ y, $ where $0 \le x \le y \le 10^9$. The query $\texttt{+ x y}$ means that the pair $(x, y)$ is added to the set. The query $\texttt{- x y}$ means that one pair $(x, y)$ is removed from the set. It is guaranteed that at the moment of such a query, there exists at least one such pair in the set.

Print $q + 1$ integers. The first integer is the maximum value of $ \operatorname{mex}(A) + \operatorname{mex}(B) $ for the initial set of pairs. Then, after each query, print the maximum value of $ \operatorname{mex}(A) + \operatorname{mex}(B) $ for the current set of pairs. Print each answer on a separate line.

In the first example, for the initial set of pairs it is optimal to choose, for example, $A = [0, 2, 1, 4, 3]$, $B = [1, 0, 1, 5, 2]$. Then $\operatorname{mex}(A) = 5$, $\operatorname{mex}(B) = 3$, and the sum is $8$. After adding the pair $(4, 5)$, one can, for example, choose $A = [0, 2, 1, 5, 3, 4]$, $B = [1, 0, 1, 4, 2, 5]$, then $\operatorname{mex}(A) = 6$, $\operatorname{mex}(B) = 3$, and the sum is $9$. In the second example, the multiset of values is $\{0, 0, 1, 1, 1, 1, 1, 1, 1, 1\}$. It is optimal, for example, to choose $A = [1, 1, 1, 1, 0]$, $B = [1, 1, 1, 1, 0]$. Then $\operatorname{mex}(A) = \operatorname{mex}(B) = 2$, and the sum is $4$. In the third example, none of the values is equal to $0$, so no choice can make $0 \in A$ or $0 \in B$. Therefore, $\operatorname{mex}(A) = \operatorname{mex}(B) = 0$, and the sum is $0$. In the fourth example, it is optimal, for example, to choose $A = [2, 3, 0, 3, 10]$, $B = [2, 3, 1, 4, 0]$. Then $\operatorname{mex}(A) = 1$, $\operatorname{mex}(B) = 5$, and the sum is $6$. In the fifth example, it is optimal, for example, to choose $A = [3, 4, 9, 0, 6]$, $B = [1, 5, 0, 0, 5]$. Then $\operatorname{mex}(A) = 1$, $\operatorname{mex}(B) = 2$, and the sum is $3$. ### Scoring - ($2$ points): $n \le 20$, $q = 0$; - ($7$ points): $b_i = 10^9$ for all initial pairs, and $y = 10^9$ for all queries; - ($8$ points): $a_i = 0$ for all initial pairs, and $x = 0$ for all queries; - ($9$ points): $n \le 500$, $q \le 500$; - ($11$ points): $q = 0$; - ($10$ points): all queries have the form $\texttt{+ x y}$; - ($9$ points): all queries have the form $\texttt{- x y}$; - ($13$ points): at any moment, for any three pairs from the current set, if the first pair shares a number with the second pair, and the second pair shares a number with the third pair, then there exists a number that belongs to all three pairs; - ($20$ points): $n, q \le 10^5$; - ($11$ points): without additional constraints.