codeforces-scrape

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

1878D.md (4148B)


      1 Source: https://codeforces.com/problemset/problem/1878/D
      2 
      3 D. Reverse Madness
      4 
      5 time limit per test
      6 
      7 1 second
      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 You are given a string $s$ of length $n$, containing lowercase Latin letters.
     22 
     23 Next you will be given a positive integer $k$ and two arrays, $l$ and $r$ of length $k$.
     24 
     25 It is guaranteed that the following conditions hold for these 2 arrays:
     26 
     27 * $l_1 = 1$;
     28 * $r_k = n$;
     29 * $l_i \le r_i$, for each positive integer $i$ such that $1 \le i \le k$;
     30 * $l_i = r_{i-1}+1$, for each positive integer $i$ such that $2 \le i \le k$;
     31 
     32 Now you will be given a positive integer $q$ which represents the number of modifications you need to do on $s$.
     33 
     34 Each modification is defined with one positive integer $x$:
     35 
     36 * Find an index $i$ such that $l_i \le x \le r_i$ (notice that such $i$ is unique).
     37 * Let $a=\min(x, r_i+l_i-x)$ and let $b=\max(x, r_i+l_i-x)$.
     38 * Reverse the substring of $s$ from index $a$ to index $b$.
     39 
     40 Reversing the substring $[a, b]$ of a string $s$ means to make $s$ equal to $s_1, s_2, \dots, s_{a-1},\ s_b, s_{b-1}, \dots, s_{a+1}, s_a,\ s_{b+1}, s_{b+2}, \dots, s_{n-1}, s_n$.
     41 
     42 Print $s$ after the last modification is finished.
     43 
     44 Input
     45 
     46 Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Description of the test cases follows.
     47 
     48 The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 2\cdot 10^5$) — the length of the string $s$, and the length of arrays $l$ and $r$.
     49 
     50 The second line of each test case contains the string $s$ ($ |s| = n$) containing lowercase Latin letters — the initial string.
     51 
     52 The third line of each test case contains $k$ positive integers $l_1, l_2, \dots, l_k$ ($1 \le l_i \le n$) — the array $l$.
     53 
     54 The fourth line of each test case contains $k$ positive integers $r_1, r_2, \dots, r_k$ ($1 \le r_i \le n$) — the array $r$.
     55 
     56 The fifth line of each test case contains a positive integer $q$ ($1 \le q \le 2 \cdot 10^5 $) — the number of modifications you need to do to $s$.
     57 
     58 The sixth line of each test case contains $q$ positive integers $x_1, x_2, \dots, x_q$ ($1\le x_i \le n$) — the description of the modifications.
     59 
     60 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.
     61 
     62 It is guaranteed that the sum of $q$ over all test cases does not exceed $2\cdot10^5$.
     63 
     64 It is guaranteed that the conditions in the statement hold for the arrays $l$ and $r$.
     65 
     66 Output
     67 
     68 For each test case, in a new line, output the string $s$ after the last modification is done.
     69 
     70 Example
     71 
     72 Input
     73 
     74 ```
     75 5
     76 
     77 4 2
     78 
     79 abcd
     80 
     81 1 3
     82 
     83 2 4
     84 
     85 2
     86 
     87 1 3
     88 
     89 5 3
     90 
     91 abcde
     92 
     93 1 2 3
     94 
     95 1 2 5
     96 
     97 3
     98 
     99 1 2 3
    100 
    101 3 1
    102 
    103 gaf
    104 
    105 1
    106 
    107 3
    108 
    109 2
    110 
    111 2 2
    112 
    113 10 1
    114 
    115 aghcdegdij
    116 
    117 1
    118 
    119 10
    120 
    121 5
    122 
    123 1 2 3 4 2
    124 
    125 1 1
    126 
    127 a
    128 
    129 1
    130 
    131 1
    132 
    133 1
    134 
    135 1
    136 ```
    137 
    138 Output
    139 
    140 ```
    141 badc
    142 abedc
    143 gaf
    144 jihgedcdga
    145 a
    146 ```
    147 
    148 Note
    149 
    150 In the first test case:
    151 
    152 The initial string is "abcd". In the first modification, we have $x=1$. Since $l_1=1\leq x \leq r_1=2$, we find the index $i = 1$. We reverse the substring from index $x=1$ to $l_1+r_1-x=1+2-1=2$. After this modification, our string is "bacd".
    153 
    154 In the second modification (and the last modification), we have $x=3$. Since $l_2=3\leq x \leq r_2=4$, we find the index $i = 2$. We reverse the substring from index $x=3$ to $l_2+r_2-x=3+4-3=4$. After this modification, our string is "badc".
    155 
    156 In the second test case:
    157 
    158 The initial string is "abcde". In the first modification, we have $x=1$. Since $l_1=1\leq x \leq r_1=1$, we find the index $i = 1$. We reverse the substring from index $x=1$ to $l_1+r_1-x=1+1-1=1$. After this modification, our string hasn't changed ("abcde").
    159 
    160 In the second modification, we have $x=2$. Since $l_2=2\leq x \leq r_2=2$, we find the index $i = 2$. We reverse the substring from index $x=2$ to $l_2+r_2-x=2+2-2=2$. After this modification, our string hasn't changed ("abcde").
    161 
    162 In the third modification (and the last modification), we have $x=3$. Since $l_3=3\leq x \leq r_3=5$, we find the index $i = 3$. We reverse the substring from index $x=3$ to $l_3+r_3-x=3+5-3=5$. After this modification, our string is "abedc".