codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.