A16201. Reverse Madness
编程题
普及/提高-
知识点
题目描述
You are given a string $s$ of length $n$ , containing lowercase Latin letters.
Next you will be given a positive integer $k$ and two arrays, $l$ and $r$ of length $k$ .
It is guaranteed that the following conditions hold for these 2 arrays:
- $l_1 = 1$ ;
- $r_k = n$ ;
- $l_i \le r_i$ , for each positive integer $i$ such that $1 \le i \le k$ ;
- $l_i = r_{i-1}+1$ , for each positive integer $i$ such that $2 \le i \le k$ ;
Now you will be given a positive integer $q$ which represents the number of modifications you need to do on $s$ .
Each modification is defined with one positive integer $x$ :
- Find an index $i$ such that $l_i \le x \le r_i$ (notice that such $i$ is unique).
- Let $a=\min(x, r_i+l_i-x)$ and let $b=\max(x, r_i+l_i-x)$ .
- Reverse the substring of $s$ from index $a$ to index $b$ .
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$ .
Print $s$ after the last modification is finished.
Next you will be given a positive integer $k$ and two arrays, $l$ and $r$ of length $k$ .
It is guaranteed that the following conditions hold for these 2 arrays:
- $l_1 = 1$ ;
- $r_k = n$ ;
- $l_i \le r_i$ , for each positive integer $i$ such that $1 \le i \le k$ ;
- $l_i = r_{i-1}+1$ , for each positive integer $i$ such that $2 \le i \le k$ ;
Now you will be given a positive integer $q$ which represents the number of modifications you need to do on $s$ .
Each modification is defined with one positive integer $x$ :
- Find an index $i$ such that $l_i \le x \le r_i$ (notice that such $i$ is unique).
- Let $a=\min(x, r_i+l_i-x)$ and let $b=\max(x, r_i+l_i-x)$ .
- Reverse the substring of $s$ from index $a$ to index $b$ .
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$ .
Print $s$ after the last modification is finished.
输入格式
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.
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$ .
The second line of each test case contains the string $s$ ( $ |s| = n$ ) containing lowercase Latin letters — the initial string.
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$ .
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$ .
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$ .
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.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$ .
It is guaranteed that the sum of $q$ over all test cases does not exceed $2\cdot10^5$ .
It is guaranteed that the conditions in the statement hold for the arrays $l$ and $r$ .
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$ .
The second line of each test case contains the string $s$ ( $ |s| = n$ ) containing lowercase Latin letters — the initial string.
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$ .
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$ .
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$ .
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.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$ .
It is guaranteed that the sum of $q$ over all test cases does not exceed $2\cdot10^5$ .
It is guaranteed that the conditions in the statement hold for the arrays $l$ and $r$ .
输出格式
For each test case, in a new line, output the string $s$ after the last modification is done.
输入输出样例
输入 #1
5 4 2 abcd 1 3 2 4 2 1 3 5 3 abcde 1 2 3 1 2 5 3 1 2 3 3 1 gaf 1 3 2 2 2 10 1 aghcdegdij 1 10 5 1 2 3 4 2 1 1 a 1 1 1 1
输出 #1
badc abedc gaf jihgedcdga a
说明/提示
In the first test case:
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".
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".
In the second test case:
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").
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").
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".
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".
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".
In the second test case:
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").
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").
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".