P13994 【MX-X19-T3】「LAOI-14」Another Round

Given a positive integer $n$ and two integer sequences $a = (a_1, \ldots, a_n)$ and $b = (b_1, \ldots, b_n)$ of length $n$, where $b_i$ is guaranteed to be non-negative, but $a_i$ may be negative. Define the notation $[n]$ to represent the set $\{ i \mid 1 \le i \le n \}$. For each $k \in [n]$, you need to select a subset $S$ of $[n]$ with size $k$. Under this constraint, find the maximum value of $$\Bigl( \max_{i \in S} a_i \Bigr) - \Bigl( \operatorname*{mex}_{i \in S} b_i \Bigr).$$ Note: $\displaystyle \operatorname*{mex}_{i \in S} b_i$ denotes the minimum non-negative integer that does not appear in $\{ b_i \mid i \in S \}$.

**The input contains multiple test cases.** The first line contains an integer $T$, indicating the number of test cases. For each test case: - The first line contains a positive integer $n$. - The second line contains $n$ integers $a_1, \ldots, a_n$. - The third line contains $n$ non-negative integers $b_1, \ldots, b_n$.

For each test case, output $n$ lines. The $i$-th line should contain one integer, which is the answer when $k = i$.

**【Sample Explanation #1】** When $k=1$, let $S = \{3\}$, then the answer is $3 - 0 = 3$. When $k=2$, let $S = \{2, 3\}$, then the answer is $3 - 2 = 1$. When $k=3$, let $S = \{1, 2, 3\}$, then the answer is $3 - 2 = 1$. **【Data Range】** **This problem uses bundled testing.** | Subtask ID | $\sum n \le$ | Special Properties | Score | |:-:|:-:|:-:|:-:| | $1$ | $10$ | C | $11$ | | $2$ | $200$ | C | $17$ | | $3$ | $2000$ | C | $23$ | | $4$ | $10^6$ | AC | $19$ | | $5$ | $10^6$ | BC | $7$ | | $6$ | $10^5$ | C | $22$ | | $7$ | $10^6$ | None | $1$ | - Special Property A: $a_i = 0$. - Special Property B: $b_i = 0$. - Special Property C: $T = 1$. For all test cases, $1 \le T, n, \sum n \le 10^6$, $-10^{9} \le a_i \le 10^{9}$, $0 \le b_i \le 10^{9}$. *Translated by DeepSeek V3.1*