CF1878D Reverse Madness

给定一个长度为 $n$ 的字符串 $s$，其中包含小写拉丁字母。 接下来给定一个正整数 $k$ 和两个长度为 $k$ 的数组 $l$ 和 $r$。 保证这两个数组满足以下条件： - $l_1 = 1$； - $r_k = n$； - 对于每个 $1 \leq i \leq k$，都有 $l_i \leq r_i$； - 对于每个 $2 \leq i \leq k$，都有 $l_i = r_{i-1} + 1$。 现在给定一个正整数 $q$，表示你需要对 $s$ 进行 $q$ 次修改。 每次修改由一个正整数 $x$ 定义： - 找到唯一的下标 $i$，使得 $l_i \leq x \leq r_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}, \dots, s_{n-1}, s_n$。 请在所有修改完成后，输出最终的字符串 $s$。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。每组测试用例的描述如下： 每组测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \leq k \leq n \leq 2 \cdot 10^5$），分别表示字符串 $s$ 的长度和数组 $l$、$r$ 的长度。 第二行包含一个长度为 $n$ 的字符串 $s$，仅包含小写拉丁字母。 第三行包含 $k$ 个正整数 $l_1, l_2, \dots, l_k$（$1 \leq l_i \leq n$），表示数组 $l$。 第四行包含 $k$ 个正整数 $r_1, r_2, \dots, r_k$（$1 \leq r_i \leq n$），表示数组 $r$。 第五行包含一个正整数 $q$（$1 \leq q \leq 2 \cdot 10^5$），表示需要对 $s$ 进行的修改次数。 第六行包含 $q$ 个正整数 $x_1, x_2, \dots, x_q$（$1 \leq x_i \leq n$），表示每次修改的位置。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。 保证所有测试用例中 $q$ 的总和不超过 $2 \cdot 10^5$。 保证数组 $l$ 和 $r$ 满足题目中的所有条件。

对于每组测试用例，输出一行，表示所有修改完成后得到的字符串 $s$。

在第一个测试用例中： 初始字符串为 "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"。 由 ChatGPT 4.1 翻译