← 返回题目列表

Codeforces · 1878/D

D. 反向疯狂

中文机器翻译题面 查看原题

给你一个长度为 $$$n$$$ 的字符串 $$$s$$$,包含小写拉丁字母。

接下来,您将得到一个正整数 $$$k$$$ 和两个数组,$$$l$$$ 和 $$$r$$$,长度为 $$$k$$$。

这 2 个数组保证满足以下条件:

- $$$l_1 = 1$$$;
- $$$r_k = n$$$;
- $$$l_i \le r_i$$$,对于每个正整数 $$$i$$$ 使得 $$$1 \le i \le k$$$;
- $$$l_i = r_{i-1}+1$$$,对于每个正整数 $$$i$$$ 使得 $$$2 \le i \le k$$$;

现在您将得到一个正整数 $$$q$$$,它代表您需要对 $$$s$$$ 进行的修改次数。

每个修改都用一个正整数 $$$x$$$ 定义:

- 找到一个索引 $$$i$$$ 使得 $$$l_i \le x \le r_i$$$ (注意这样的 $$$i$$$ 是唯一的)。
- 让 $$$a=\min(x, r_i+l_i-x)$$$ 并让 $$$b=\max(x, r_i+l_i-x)$$$。
- 将 $$$s$$$ 的子字符串从索引 $$$a$$$ 反转到索引 $$$b$$$。

反转字符串 $$$s$$$ 的子串 $$$[a, b]$$$ 意味着使 $$$s$$$ 等于 $$$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}、\点、s_{n-1}、s_n$$$。

最后一次修改完成后打印$$$s$$$。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 2\cdot 10^5$$$) - 字符串 $$$s$$$ 的长度,以及数组 $$$l$$$ 和 $$$r$$$ 的长度。

每个测试用例的第二行包含字符串 $$$s$$$ ($$$ |s| = n$$$),其中包含小写拉丁字母 - 初始字符串。

每个测试用例的第三行包含 $$$k$$$ 正整数 $$$l_1, l_2, \dots, l_k$$$ ($$$1 \le l_i \le n$$$) — 数组 $$$l$$$。

每个测试用例的第四行包含 $$$k$$$ 正整数 $$$r_1, r_2, \dots, r_k$$$ ($$$1 \le r_i \le n$$$) — 数组 $$$r$$$。

每个测试用例的第五行包含一个正整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5 $$$) - 您需要对 $$$s$$$ 进行的修改数量。

每个测试用例的第六行包含 $$$q$$$ 正整数 $$$x_1, x_2, \dots, x_q$$$ ($$$1\le x_i \le n$$$) — 修改的描述。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。

保证所有测试用例的 $$$q$$$ 总和不超过 $$$2\cdot10^5$$$。

保证语句中的条件对于数组 $$$l$$$ 和 $$$r$$$ 成立。

输出

对于每个测试用例,在新行中输出最后一次修改完成后的字符串 $$$s$$$。

示例

输入 #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

注意

在第一个测试用例中:

初始字符串是“abcd”。在第一个修改中,我们有 $$$x=1$$$。由于$$$l_1=1\leq x \leq r_1=2$$$,我们找到索引$$$i = 1$$$。我们将子字符串从索引 $$$x=1$$$ 反转为 $$$l_1+r_1-x=1+2-1=2$$$。修改后,我们的字符串是“bacd”。

在第二次修改(也是最后一次修改)中,我们有 $$$x=3$$$。由于$$$l_2=3\leq x \leq r_2=4$$$,我们找到索引$$$i = 2$$$。我们将子字符串从索引 $$$x=3$$$ 反转为 $$$l_2+r_2-x=3+4-3=4$$$。修改后,我们的字符串是“badc”。

在第二个测试用例中:

初始字符串是“abcde”。在第一个修改中,我们有 $$$x=1$$$。由于$$$l_1=1\leq x \leq r_1=1$$$,我们找到索引$$$i = 1$$$。我们将子字符串从索引 $$$x=1$$$ 反转为 $$$l_1+r_1-x=1+1-1=1$$$。修改后,我们的字符串没有改变(“abcde”)。

在第二个修改中,我们有 $$$x=2$$$。由于 $$$l_2=2\leq x \leq r_2=2$$$,我们找到索引 $$$i = 2$$$。我们将子字符串从索引 $$$x=2$$$ 反转为 $$$l_2+r_2-x=2+2-2=2$$$。修改后,我们的字符串没有改变(“abcde”)。

在第三次修改(也是最后一次修改)中,我们有 $$$x=3$$$。由于 $$$l_3=3\leq x \leq r_3=5$$$,我们找到索引 $$$i = 3$$$。我们将子字符串从索引 $$$x=3$$$ 反转为 $$$l_3+r_3-x=3+5-3=5$$$。修改后,我们的字符串是“abedc”。