CF1213F Unstable String Sort

作者构造了一个由 $n$ 个小写拉丁字母组成的字符串 $s$。 你得到了它的两个下标排列（不一定相同）$p$ 和 $q$（长度均为 $n$）。排列是长度为 $n$ 的数组，包含 $1$ 到 $n$ 的每个整数恰好一次。 对于所有 $i$ 从 $1$ 到 $n-1$，都有：$s[p_i] \le s[p_{i + 1}]$ 且 $s[q_i] \le s[q_{i + 1}]$。也就是说，如果你按照排列下标的顺序写出 $s$ 的所有字符，得到的字符串是非递减排序的。 你的任务是还原出任意一个满足上述条件、长度为 $n$、且包含至少 $k$ 个不同小写拉丁字母的字符串 $s$。 如果有多种答案，你可以输出任意一种。

输入的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5, 1 \le k \le 26$），分别表示字符串的长度和要求的不同字符的数量。 第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$，所有 $p_i$ 是 $1$ 到 $n$ 的不重复整数），表示排列 $p$。 第三行包含 $n$ 个整数 $q_1, q_2, \dots, q_n$（$1 \le q_i \le n$，所有 $q_i$ 是 $1$ 到 $n$ 的不重复整数），表示排列 $q$。

如果不存在满足条件的字符串，第一行输出 "NO"。 否则，第一行输出 "YES"，第二行输出字符串 $s$。$s$ 由 $n$ 个小写拉丁字母组成，包含至少 $k$ 个不同字符，并且满足给定的排列条件。 如果有多种答案，你可以输出任意一种。

由 ChatGPT 4.1 翻译