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