310331: CF1819A. Constructive Problem
Description
As you know, any problem that does not require the use of complex data structures is considered constructive. You are offered to solve one of such problems.
You are given an array $a$ of $n$ non-negative integers. You are allowed to perform the following operation exactly once: choose some non-empty subsegment $a_l, a_{l+1}, \ldots, a_r$ of the array $a$ and a non-negative integer $k$, and assign value $k$ to all elements of the array on the chosen subsegment.
The task is to find out whether $\operatorname{MEX}(a)$ can be increased by exactly one by performing such an operation. In other words, if before the operation $\operatorname{MEX}(a) = m$ held, then after the operation it must hold that $\operatorname{MEX}(a) = m + 1$.
Recall that $\operatorname{MEX}$ of a set of integers $c_1, c_2, \ldots, c_k$ is defined as the smallest non-negative integer $x$ which does not occur in the set $c$.
InputEach test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 50\,000$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $n$ ($1 \le n \le 200\,000$) — the number of elements of array $a$.
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — elements of array $a$.
It is guaranteed that the sum $n$ over all test cases does not exceed $200\,000$.
OutputFor each test case, print "Yes" if you can increase $\operatorname{MEX}(a)$ by exactly one by performing the operation from the statement exactly once, otherwise print "No".
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
ExampleInput4 3 1 2 1 4 0 2 2 0 4 3 2 0 2 1 0Output
Yes Yes No NoNote
In the first test case, $\operatorname{MEX}(a) = 0$. If you set all elements of $a$ to $0$, then $\operatorname{MEX}$ of the resulting array will be $1$, and thus will increase by one.
In the second test case, $\operatorname{MEX}(a) = 1$. If we assign a value of $1$ to the elements of $a$ on a subsegment from $2$ to $3$, we get an array $[0, 1, 1, 0]$ for which $\operatorname{MEX}$ is $2$, and thus is increased by one compared to the original.
It can be shown that in the third and fourth test cases it is impossible to perform an operation so that the value of $\operatorname{MEX}(a)$ increases by exactly one.
Input
题意翻译
### 题目描述 给定整数 $n$ 和一个非负整数序列 $a$。 对于非负整数序列 $c$，记 $\text{MEX}(c)$ 表示**不存在**于 $c$ 中的最小非负整数。 记初始时 $m=\text{MEX}(a)$。 你需要进行下列操作恰好一次： - 选择整数 $l,r,k(1\leq l\leq r\leq n;0\leq k)$，然后将 $a_l,a_{l+1},\cdots,a_r$ 的值均变为 $k$。 判断能否通过恰好一次上述操作使操作后的 $a$ 满足 $\text{MEX}(a)=m+1$。 能输出 `Yes`，不能输出 `No`。 每个测试点包含 $t$ 组数据。 ### 输入格式 第一行输入一个整数 $t(1\leq t\leq5\times10^4)$ 表示数据组数，接下来对于每组数据： 第一行输入一个整数 $n(1\leq n,\sum n\leq2\times10^5)$。 接下来输入一行 $n$ 个整数 $a_1,a_2,\cdots,a_n(0\leq a_i\leq10^9)$。 ### 输出格式 对于每组数据： 如果能通过一次操作满足要求，输出 `Yes`；否则输出 `No`。 实际评测时校验器对大小写不敏感。 ### 样例解释 对于第一组数据： - 初始 $m=0$。 你可以选择 $l=1,r=3,k=0$，此后 $a=[0,0,0],\text{MEX}(a)=1=m+1$。 因此可以通过一次操作达成要求，答案为 `Yes`。 对于第二组数据： - 初始 $m=1$。 你可以选择 $l=2,r=3,k=1$，此后 $a=[0,1,1,0],\text{MEX}(a)=2=m+1$。 因此可以通过一次操作达成要求，答案为 `Yes`。 可以证明，在第三组和第四组数据中，我们不能通过一次操作达成要求，因此这两组数据的答案为 `No`。Output
这是一个建设性问题，不需要使用复杂数据结构。给定一个由非负整数组成的数组a，你可以执行一次以下操作：选择数组a的一个非空子段a_l, a_{l+1}, …, a_r和一个非负整数k，并将值k赋给所选子段上的数组的所有元素。任务是找出是否可以通过执行这样的操作将MEX(a)（即数组a的最小非负整数x，该整数不在集合a中）增加一个单位。换句话说，如果操作前MEX(a)=m，那么操作后必须满足MEX(a)=m+1。
输入数据格式：
每个测试包含多个测试用例。第一行包含测试用例数t（1≤t≤50,000）。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数n（1≤n≤200,000）——数组a的元素数量。
每个测试用例的第二行包含n个整数a_1, a_2, …, a_n（0≤a_i≤10^9）——数组a的元素。
保证所有测试用例的n之和不超过200,000。
输出数据格式：
对于每个测试用例，如果你可以通过执行题目描述中的操作精确一次将MEX(a)增加一个单位，则打印"Yes"，否则打印"No"。
输出答案时大小写不敏感，例如："yEs"、"yes"、"Yes"和"YES"都将被视为肯定回答。
示例：
输入：
4
3
1 2 1
4
0 2 2 0
4
3 2 0 2
1
0
输出：
Yes
Yes
No
No
注意：
在第一个测试用例中，MEX(a)=0。如果将a的所有元素设置为0，则所得数组的MEX为1，因此增加了一个单位。
在第二个测试用例中，MEX(a)=1。如果我们给a的一个从2到3的子段上的元素赋值为1，我们得到一个数组[0, 1, 1, 0]，其MEX为2，因此比原始数组增加了一个单位。
可以证明，在第三个和第四个测试用例中，不可能执行一个操作，使得MEX(a)的值恰好增加一个单位。题目大意： 这是一个建设性问题，不需要使用复杂数据结构。给定一个由非负整数组成的数组a，你可以执行一次以下操作：选择数组a的一个非空子段a_l, a_{l+1}, …, a_r和一个非负整数k，并将值k赋给所选子段上的数组的所有元素。任务是找出是否可以通过执行这样的操作将MEX(a)（即数组a的最小非负整数x，该整数不在集合a中）增加一个单位。换句话说，如果操作前MEX(a)=m，那么操作后必须满足MEX(a)=m+1。 输入数据格式： 每个测试包含多个测试用例。第一行包含测试用例数t（1≤t≤50,000）。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n（1≤n≤200,000）——数组a的元素数量。 每个测试用例的第二行包含n个整数a_1, a_2, …, a_n（0≤a_i≤10^9）——数组a的元素。 保证所有测试用例的n之和不超过200,000。 输出数据格式： 对于每个测试用例，如果你可以通过执行题目描述中的操作精确一次将MEX(a)增加一个单位，则打印"Yes"，否则打印"No"。 输出答案时大小写不敏感，例如："yEs"、"yes"、"Yes"和"YES"都将被视为肯定回答。 示例： 输入： 4 3 1 2 1 4 0 2 2 0 4 3 2 0 2 1 0 输出： Yes Yes No No 注意： 在第一个测试用例中，MEX(a)=0。如果将a的所有元素设置为0，则所得数组的MEX为1，因此增加了一个单位。 在第二个测试用例中，MEX(a)=1。如果我们给a的一个从2到3的子段上的元素赋值为1，我们得到一个数组[0, 1, 1, 0]，其MEX为2，因此比原始数组增加了一个单位。 可以证明，在第三个和第四个测试用例中，不可能执行一个操作，使得MEX(a)的值恰好增加一个单位。