Reverse Madness (Codeforces 1878D)
Tags: Greedy, data structures

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.

Input: 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$$$.

Output: For each test case, in a new line, output the string $$$s$$$ after the last modification is done.

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

Sample Inputs:
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

Sample Outputs:
badc
abedc
gaf
jihgedcdga
a

Solution (Python):
t = int(input())
st = ''
for i in range(t):
    (n, k) = map(int, input().split())
    s = list(input())
    l = list(map(int, input().split()))
    r = list(map(int, input().split()))
    q = int(input())
    xl = list(map(int, input().split()))
    lst = [0] * n
    for x in xl:
        lst[x - 1] += 1
    for j in range(k):
        a1 = l[j] - 1
        b1 = r[j] - 1
        num = 0
        while a1 < b1:
            num += lst[a1] + lst[b1]
            if num % 2:
                (s[a1], s[b1]) = (s[b1], s[a1])
            a1 += 1
            b1 -= 1
    st += ''.join(s)
    if i != t - 1:
        st += '\n'
print(st)

Solution (Python):
import sys

def solute(s, l, r, x):
    s = list(s)
    x.sort(reverse=True)
    for (l1, r1) in zip(l, r):
        l1 -= 1
        r1 -= 1
        counter = [0] * ((r1 - l1 + 1) // 2)
        while x and x[-1] - 1 <= r1:
            curr = x.pop() - 1 - l1
            if curr < len(counter):
                counter[curr] += 1
            elif r1 - l1 - curr < len(counter):
                counter[r1 - l1 - curr] += 1
        cum = 0
        for (i, c) in enumerate(counter):
            cum = (cum + c) % 2
            if cum:
                (s[l1 + i], s[r1 - i]) = (s[r1 - i], s[l1 + i])
    return ''.join(s)
t = int(sys.stdin.readline())
for _ in range(t):
    (n, k) = map(int, sys.stdin.readline().strip().split())
    s = sys.stdin.readline().strip()
    l = list(map(int, sys.stdin.readline().strip().split()))
    r = list(map(int, sys.stdin.readline().strip().split()))
    q = int(sys.stdin.readline().strip())
    x = list(map(int, sys.stdin.readline().strip().split()))
    print(solute(s, l, r, x))

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, k) = readInts()
    (s, L, R, q, X) = (readStr(), readList(), readList(), readInt(), readList())
    freq = [0] * (n + 1)
    for x in X:
        freq[x] += 1
    ps = [0] * (n + 1)
    for i in range(1, n + 1):
        ps[i] = ps[i - 1] + freq[i]
    ans = [''] + list(s)
    for i in range(k):
        (l, r) = (L[i], R[i])
        mid = (l + r) // 2
        for j in range(l, mid + 1):
            cnt = (ps[j] - ps[l - 1] + ps[r] - ps[l + r - j - 1]) % 2
            if cnt:
                (ans[j], ans[l + r - j]) = (ans[l + r - j], ans[j])
    return ''.join(ans[1:])
for _ in range(int(input())):
    print(solve())