2123E.md (2056B)
1 Source: https://codeforces.com/problemset/problem/2123/E 2 3 E. MEX Count 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Define the $\mathrm{MEX}$ (minimum excluded value) of an array to be the smallest nonnegative integer not present in the array. For example, 22 23 * $\mathrm{MEX}([2, 2, 1]) = 0$ because $0$ is not in the array. 24 * $\mathrm{MEX}([3, 1, 0, 1]) = 2$ because $0$ and $1$ are in the array but $2$ is not. 25 * $\mathrm{MEX}([0, 3, 1, 2]) = 4$ because $0$, $1$, $2$, and $3$ are in the array but $4$ is not. 26 27 You are given an array $a$ of size $n$ of nonnegative integers. 28 29 For all $k$ ($0\leq k \leq n$), count the number of possible values of $\mathrm{MEX}(a)$ after removing exactly $k$ values from $a$. 30 31 Input 32 33 The first line contains an integer $t$ ($1\leq t\leq 10^4$) — the number of test cases. 34 35 The first line of each test case contains one integer $n$ ($1\leq n\leq 2\cdot 10^5$) — the size of the array $a$. 36 37 The second line of each test case contains $n$ integers, $a_1,a_2,\dots,a_n$ ($0\leq a_i\leq n$). 38 39 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$. 40 41 Output 42 43 For each test case, output a single line containing $n+1$ integers — the number of possible values of $\mathrm{MEX}(a)$ after removing exactly $k$ values, for $k=0,1,\dots,n$. 44 45 Example 46 47 Input 48 49 ``` 50 5 51 52 5 53 54 1 0 0 1 2 55 56 6 57 58 3 2 0 4 5 1 59 60 6 61 62 1 2 0 1 3 2 63 64 4 65 66 0 3 4 1 67 68 5 69 70 0 0 0 0 0 71 ``` 72 73 Output 74 75 ``` 76 1 2 4 3 2 1 77 1 6 5 4 3 2 1 78 1 3 5 4 3 2 1 79 1 3 3 2 1 80 1 1 1 1 1 1 81 ``` 82 83 Note 84 85 In the first sample, consider $k=1$. If you remove a $0$, then you get the following array: 86 87 | | | | | 88 | --- | --- | --- | --- | 89 | 1 | 0 | 1 | 2 | 90 91 So we get $\mathrm{MEX}(a) = 3$. Alternatively, if you remove the $2$, then you get the following array: 92 93 | | | | | 94 | --- | --- | --- | --- | 95 | 1 | 0 | 0 | 1 | 96 97 So we get $\mathrm{MEX}(a) = 2$. It can be shown that these are the only possible values of $\mathrm{MEX}(a)$ after removing exactly one value. So the output for $k=1$ is $2$.