310787: CF1887F. Minimum Segments
Description
You had a sequence $a_1, a_2, \ldots, a_n$ consisting of integers from $1$ to $n$, not necessarily distinct. For some unknown reason, you decided to calculate the following characteristic of the sequence:
- Let $r_i$ ($1 \le i \le n$) be the smallest $j \ge i$ such that on the subsegment $a_i, a_{i+1}, \ldots, a_j$ all distinct numbers from the sequence $a$ appear. More formally, for any $k \in [1, n]$, there exists $l \in [i, j]$ such that $a_k = a_l$. If such $j$ does not exist, $r_i$ is considered to be equal to $n+1$.
- The characteristic of the sequence $a$ is defined as the sequence $r_1, r_2, \ldots, r_n$.
Each test consist of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the lost sequence $a$.
The second line of each test case contains $n$ integers $r_1, r_2, \ldots, r_n$ ($i \le r_i \le n+1$) — the characteristic of the lost sequence $a$.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
OutputFor each test case, output the following:
- If there is no sequence $a$ with the characteristic $r$, print "No".
- Otherwise, print "Yes" on the first line, and on the second line, print any sequence of integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) that matches the characteristic $r$.
5 3 2 3 4 5 2 3 5 4 6 1 1 3 1 3 4 8 3 6 6 6 8 9 9 9Output
Yes 1 2 1 No Yes 1 No Yes 1 3 5 3 5 1 1 3Note
In the first test case, the sequence $a = [1, 2, 1]$ is suitable. The integers $1$ and $2$ appear on the subsegments $[1, 2]$ and $[2, 3]$.
In the second test case, it can be proved that there is no suitable sequence $a$.
Output
你有一个由整数组成的序列 $ a_1, a_2, \ldots, a_n $（不一定互不相同），其中的整数范围从 1 到 $ n $。出于某种未知原因，你决定计算序列的以下特征：
1. 令 $ r_i $（$ 1 \le i \le n $）是满足条件的最小的 $ j \ge i $，即子序列 $ a_i, a_{i+1}, \ldots, a_j $ 包含序列 $ a $ 中的所有不同的数。更正式地说，对于任意 $ k \in [1, n] $，存在 $ l \in [i, j] $ 使得 $ a_k = a_l $。如果这样的 $ j $ 不存在，$ r_i $ 被认为是等于 $ n+1 $。
2. 序列 $ a $ 的特征定义为序列 $ r_1, r_2, \ldots, r_n $。
不幸的是，序列 $ a $ 丢失了，但你仍然有它的特征 $ r $。你想要重建任何匹配特征的序列 $ a $，或者确定特征中存在错误且这样的序列不存在。
输入数据格式：
每个测试包含多个测试用例。第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $）——测试用例的数量。接下来是测试用例的描述。
每个测试用例的第一行包含一个整数 $ n $（$ 1 \le n \le 2 \cdot 10^5 $）——丢失序列 $ a $ 的长度。
每个测试用例的第二行包含 $ n $ 个整数 $ r_1, r_2, \ldots, r_n $（$ i \le r_i \le n+1 $）——丢失序列 $ a $ 的特征。
保证所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。
输出数据格式：
对于每个测试用例，输出以下内容：
- 如果不存在具有特征 $ r $ 的序列 $ a $，打印 "No"。
- 否则，第一行打印 "Yes"，第二行打印任意匹配特征 $ r $ 的整数序列 $ a_1, a_2, \ldots, a_n $（$ 1 \le a_i \le n $）。
你可以以任何大小写组合输出 "YES" 和 "NO"。题目大意： 你有一个由整数组成的序列 $ a_1, a_2, \ldots, a_n $（不一定互不相同），其中的整数范围从 1 到 $ n $。出于某种未知原因，你决定计算序列的以下特征： 1. 令 $ r_i $（$ 1 \le i \le n $）是满足条件的最小的 $ j \ge i $，即子序列 $ a_i, a_{i+1}, \ldots, a_j $ 包含序列 $ a $ 中的所有不同的数。更正式地说，对于任意 $ k \in [1, n] $，存在 $ l \in [i, j] $ 使得 $ a_k = a_l $。如果这样的 $ j $ 不存在，$ r_i $ 被认为是等于 $ n+1 $。 2. 序列 $ a $ 的特征定义为序列 $ r_1, r_2, \ldots, r_n $。 不幸的是，序列 $ a $ 丢失了，但你仍然有它的特征 $ r $。你想要重建任何匹配特征的序列 $ a $，或者确定特征中存在错误且这样的序列不存在。 输入数据格式： 每个测试包含多个测试用例。第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $）——测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含一个整数 $ n $（$ 1 \le n \le 2 \cdot 10^5 $）——丢失序列 $ a $ 的长度。 每个测试用例的第二行包含 $ n $ 个整数 $ r_1, r_2, \ldots, r_n $（$ i \le r_i \le n+1 $）——丢失序列 $ a $ 的特征。 保证所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。 输出数据格式： 对于每个测试用例，输出以下内容： - 如果不存在具有特征 $ r $ 的序列 $ a $，打印 "No"。 - 否则，第一行打印 "Yes"，第二行打印任意匹配特征 $ r $ 的整数序列 $ a_1, a_2, \ldots, a_n $（$ 1 \le a_i \le n $）。 你可以以任何大小写组合输出 "YES" 和 "NO"。