CF1887F Minimum Segments

你有一个由 $1$ 到 $n$ 的整数构成的序列 $a_1, a_2, \ldots, a_n$，这些整数不一定互不相同。出于某种原因，你决定计算该序列的如下特征： - 令 $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$。 - 序列 $a$ 的特征定义为序列 $r_1, r_2, \ldots, r_n$。 不幸的是，序列 $a$ 丢失了，但你仍然保留着它的特征 $r$。你想要重构出任意一个与该特征匹配的序列 $a$，或者判断该特征有误，不存在这样的序列。

每个测试包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）——丢失的序列 $a$ 的长度。 第二行包含 $n$ 个整数 $r_1, r_2, \ldots, r_n$（$i \le r_i \le n+1$）——丢失序列 $a$ 的特征。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出如下内容： - 如果不存在与特征 $r$ 匹配的序列 $a$，输出 “No”。 - 否则，第一行输出 “Yes”，第二行输出任意一个满足特征 $r$ 的整数序列 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）。 你可以以任意大小写输出 “YES” 和 “NO”（例如，"yEs"、"yes"、"Yes" 和 "YES" 都会被识别为肯定答案）。

在第一个测试用例中，序列 $a = [1, 2, 1]$ 是合适的。整数 $1$ 和 $2$ 分别出现在子区间 $[1, 2]$ 和 $[2, 3]$ 中。 在第二个测试用例中，可以证明不存在合适的序列 $a$。 由 ChatGPT 4.1 翻译