CF1023D Array Restoration

最初有一个包含 $n$ 个整数的数组 $a$，其下标从 $1$ 到 $n$。 对该数组进行了恰好 $q$ 次操作。在第 $i$ 次操作中，选择了一个区间 $(l_i, r_i)$（$1 \le l_i \le r_i \le n$），并将从 $l_i$ 到 $r_i$（包括两端）内的所有元素的值都改为 $i$。操作的顺序不能改变，所有 $q$ 次操作都已执行。已知数组的每个位置都至少被某个区间覆盖过一次。 我们本可以让你判断，给定一个由 $n$ 个整数（取值范围为 $1$ 到 $q$）组成的数组，是否可以通过上述操作得到。但我们觉得这对你来说太简单了。 因此，我们对问题进行了如下增强：在最终数组中，选择了一些位置（可能为空），并将这些位置上的元素值设为 $0$。 你的任务是判断，是否可以通过上述操作得到这个数组。如果可以，请还原出一个可能的原始数组。 如果存在多种可能的原始数组，输出任意一种即可。

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 2 \times 10^5$），分别表示数组的长度和操作次数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le q$），表示最终得到的数组。如果某个位置 $j$ 上的元素为 $0$，则该位置的元素可以是 $1$ 到 $q$ 之间的任意整数。

如果可以通过 $q$ 次操作得到数组 $a$，输出 "YES"。 否则输出 "NO"。 如果可以得到，第二行输出 $n$ 个整数，第 $i$ 个数表示还原后的第 $i$ 个元素，且每个元素的值应在 $1$ 到 $q$ 之间。该数组应能通过恰好 $q$ 次操作得到。 如果存在多种可能的原始数组，输出任意一种即可。

在第一个样例中，你也可以将 $0$ 替换为 $1$，但不能替换为 $3$。 在第二个样例中，直到第 $10$ 次操作选择区间 $(1, 3)$ 之前，选择哪些区间并不重要。 第三个样例说明了操作顺序不能改变，不能先将 $(1, 3)$ 赋值为 $6$，再将 $(2, 2)$ 赋值为 $5$。$5$ 的区间必须在 $6$ 的区间之前执行。 第四个样例有很多种正确的还原数组。 由 ChatGPT 4.1 翻译