1986C.md (3207B)
1 Source: https://codeforces.com/problemset/problem/1986/C 2 3 C. Update Queries 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Let's consider the following simple problem. You are given a string $s$ of length $n$, consisting of lowercase Latin letters, as well as an array of indices $ind$ of length $m$ ($1 \leq ind_i \leq n$) and a string $c$ of length $m$, consisting of lowercase Latin letters. Then, in order, you perform the update operations, namely, during the $i$-th operation, you set $s_{ind_i} = c_i$. Note that you perform all $m$ operations from the first to the last. 22 23 Of course, if you change the order of indices in the array $ind$ and/or the order of letters in the string $c$, you can get different results. Find the lexicographically smallest string $s$ that can be obtained after $m$ update operations, if you can rearrange the indices in the array $ind$ and the letters in the string $c$ as you like. 24 25 A string $a$ is lexicographically less than a string $b$ if and only if one of the following conditions is met: 26 27 * $a$ is a prefix of $b$, but $a \neq b$; 28 * in the first position where $a$ and $b$ differ, the symbol in string $a$ is earlier in the alphabet than the corresponding symbol in string $b$. 29 30 Input 31 32 Each test consists of several sets of input data. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of sets of input data. Then follows their description. 33 34 The first line of each set of input data contains two integers $n$ and $m$ ($1 \leq n, m \leq 10^5$) — the length of the string $s$ and the number of updates. 35 36 The second line of each set of input data contains a string $s$ of length $n$, consisting of lowercase Latin letters. 37 38 The third line of each set of input data contains $m$ integers $ind_1, ind_2, \ldots, ind_m$ ($1 \leq ind_i \leq n$) — the array of indices $ind$. 39 40 The fourth line of each set of input data contains a string $c$ of length $m$, consisting of lowercase Latin letters. 41 42 It is guaranteed that the sum of $n$ over all sets of input data does not exceed $2 \cdot 10^5$. Similarly, the sum of $m$ over all sets of input data does not exceed $2 \cdot 10^5$. 43 44 Output 45 46 For each set of input data, output the lexicographically smallest string $s$ that can be obtained by rearranging the indices in the array $ind$ and the letters in the string $c$ as you like. 47 48 Example 49 50 Input 51 52 ``` 53 4 54 55 1 2 56 57 a 58 59 1 1 60 61 cb 62 63 4 4 64 65 meow 66 67 1 2 1 4 68 69 zcwz 70 71 7 4 72 73 abacaba 74 75 1 3 5 7 76 77 damn 78 79 7 10 80 81 traktor 82 83 7 6 5 4 3 2 1 6 4 2 84 85 codeforces 86 ``` 87 88 Output 89 90 ``` 91 b 92 cwoz 93 abdcmbn 94 ccdeefo 95 ``` 96 97 Note 98 99 In the first set of input data, you can leave the array $ind$ and the string $c$ unchanged and simply perform all operations in that order. 100 101 In the second set of input data, you can set the array $ind = [1, 1, 4, 2]$ and $c =$ "zczw". Then the string $s$ will change as follows: $meow \rightarrow zeow \rightarrow ceow \rightarrow ceoz \rightarrow cwoz$. 102 103 In the third set of input data, you can leave the array $ind$ unchanged and set $c = $ "admn". Then the string $s$ will change as follows: $abacaba \rightarrow abacaba \rightarrow abdcaba \rightarrow abdcmba \rightarrow abdcmbn$.