Unstable String Sort

题意翻译

# Description 作者想出了一个由小写字母组成的字符串 你有两个排列$p$,$q$ (两者长度都为$n$)。回想一下，排列是长度为$n$的数组，它包含$1$到$n$的每个整数，并且每个数只出现一次 对于从$1$到$n-1$的所有$i$满足以下的条件：$s[p_i]\leq s[p_{i+1}]$和$s[q_i]\leq s[q_{i+1}]$ 这意味着，如果你按照排列的顺序写下字符串$s$的话，字符串$s$将按照非递减顺序排序 你的任务是恢复长度为$n$的字符串$s$，该字符串至少包含$k$个不同的小写字母， 如果有多个答案，你可以输出其中任何一个。 # input 输入的第一行包含两个整数$n$和$k$ $( 1\leq n\leq 2\times 10^5,1\leq k\leq 26)$ $n$和$k$分别表示字符串的长度和所需的不同字符数。 输入的第二行包含$n$个整数$p_1,p_2,…,p_n$（$1\leq p_i\leq n$，所有$p_i$都是从$1$到$n$的不同整数） 输入的第三行包含$n$个整数$q_1,q_2,…,q_n$（$1\leq q_i\leq n$，所有$q_i$都是从$1$到$n$的不同整数） # Output 如果找不到合适的字符串，请在第一行输出"$NO$"。 否则在第一行输出"$YES$"，在第二行输出字符串$s$。它应该由$n$个小写字母组成，至少包含$k$个不同的字符，并适合给定的排列。 如果有多个答案，您可以输出其中任何一个。 # **Example** **input** ``` 3 2 1 2 3 1 3 2 ``` output ``` YES abb ```

题目描述

Authors have come up with the string $ s $ consisting of $ n $ lowercase Latin letters. You are given two permutations of its indices (not necessary equal) $ p $ and $ q $ (both of length $ n $ ). Recall that the permutation is the array of length $ n $ which contains each integer from $ 1 $ to $ n $ exactly once. For all $ i $ from $ 1 $ to $ n-1 $ the following properties hold: $ s[p_i] \le s[p_{i + 1}] $ and $ s[q_i] \le s[q_{i + 1}] $ . It means that if you will write down all characters of $ s $ in order of permutation indices, the resulting string will be sorted in the non-decreasing order. Your task is to restore any such string $ s $ of length $ n $ consisting of at least $ k $ distinct lowercase Latin letters which suits the given permutations. If there are multiple answers, you can print any of them.

输入输出格式

输入格式

The first line of the input contains two integers $ n $ and $ k $ ( $ 1 \le n \le 2 \cdot 10^5, 1 \le k \le 26 $ ) — the length of the string and the number of distinct characters required. The second line of the input contains $ n $ integers $ p_1, p_2, \dots, p_n $ ( $ 1 \le p_i \le n $ , all $ p_i $ are distinct integers from $ 1 $ to $ n $ ) — the permutation $ p $ . The third line of the input contains $ n $ integers $ q_1, q_2, \dots, q_n $ ( $ 1 \le q_i \le n $ , all $ q_i $ are distinct integers from $ 1 $ to $ n $ ) — the permutation $ q $ .

输出格式

If it is impossible to find the suitable string, print "NO" on the first line. Otherwise print "YES" on the first line and string $ s $ on the second line. It should consist of $ n $ lowercase Latin letters, contain at least $ k $ distinct characters and suit the given permutations. If there are multiple answers, you can print any of them.

输入输出样例

输入样例 #1

3 2
1 2 3
1 3 2

输出样例 #1

YES
abb