Mark and His Unfinished Essay (Codeforces 1705C)
Tags: Implement, brute force

One night, Mark realized that there is an essay due tomorrow. He hasn't written anything yet, so Mark decided to randomly copy-paste substrings from the prompt to make the essay.More formally, the prompt is a string $$$s$$$ of initial length $$$n$$$. Mark will perform the copy-pasting operation $$$c$$$ times. Each operation is described by two integers $$$l$$$ and $$$r$$$, which means that Mark will append letters $$$s_l s_{l+1} \ldots s_r$$$ to the end of string $$$s$$$. Note that the length of $$$s$$$ increases after this operation.Of course, Mark needs to be able to see what has been written. After copying, Mark will ask $$$q$$$ queries: given an integer $$$k$$$, determine the $$$k$$$-th letter of the final string $$$s$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1\leq t\leq 1000$$$) — the number of test cases.The first line of each test case contains three integers $$$n$$$, $$$c$$$, and $$$q$$$ ($$$1\leq n\leq 2\cdot 10^5$$$, $$$1\leq c\leq 40$$$, and $$$1\leq q\leq 10^4$$$) — the length of the initial string $$$s$$$, the number of copy-pasting operations, and the number of queries, respectively.The second line of each test case contains a single string $$$s$$$ of length $$$n$$$. It is guaranteed that $$$s$$$ only contains lowercase English letters.The following $$$c$$$ lines describe the copy-pasting operation. Each line contains two integers $$$l$$$ and $$$r$$$ ($$$1\leq l\leq r\leq 10^{18}$$$). It is also guaranteed that $$$r$$$ does not exceed the current length of $$$s$$$.The last $$$q$$$ lines of each test case describe the queries. Each line contains a single integer $$$k$$$ ($$$1\leq k\leq 10^{18}$$$). It is also guaranteed that $$$k$$$ does not exceed the final length of $$$s$$$.It is guaranteed that the sum of $$$n$$$ and $$$q$$$ across all test cases does not exceed $$$2\cdot 10^5$$$ and $$$10^4$$$, respectively.

Output: For each query, print the $$$k$$$-th letter of the final string $$$s$$$.

Note: In the first test case, the copy-paste process is as follows.   The first step is pasting string $$$\texttt{mark}$$$ at the end, yielding the string $$$\texttt{mark}\color{red}{\texttt{mark}}$$$.  The second step is pasting string $$$\texttt{mar}$$$ at the end, yielding the string $$$\texttt{markmark}\color{red}{\texttt{mar}}$$$.  The third step is pasting string $$$\texttt{rkmark}$$$ at the end, yielding the string $$$\texttt{markmarkmar}\color{red}{\texttt{rkmark}}$$$. In the second test case, the copy-paste process is as follows.   The first step is pasting string $$$\texttt{re}$$$ at the end, yielding the string $$$\texttt{creamii}\color{red}{\texttt{re}}$$$.  The second step is pasting string $$$\texttt{ea}$$$ at the end, yielding the string $$$\texttt{creamiire}\color{red}{\texttt{ea}}$$$.  The third step is pasting string $$$\texttt{reamiire}$$$ at the end, yielding the string $$$\texttt{creamiireea}\color{red}{\texttt{reamiire}}$$$. 

Sample Inputs:
2
4 3 3
mark
1 4
5 7
3 8
1
10
12
7 3 3
creamii
2 3
3 4
2 9
9
11
12

Sample Outputs:
m
a
r
e
a
r

Solution (Python):
def solve():
    (n, c, q) = map(int, input().split())
    s = input().strip()
    left = [0] * (c + 1)
    right = [0] * (c + 1)
    diff = [0] * (c + 1)
    left[0] = 0
    right[0] = n
    for i in range(1, c + 1):
        (l, r) = map(int, input().split())
        l -= 1
        r -= 1
        left[i] = right[i - 1]
        right[i] = left[i] + (r - l + 1)
        diff[i] = left[i] - l
    for _ in range(q):
        k = int(input())
        k -= 1
        for i in range(c, 0, -1):
            if k < left[i]:
                continue
            else:
                k -= diff[i]
        print(s[k])

def main():
    tt = int(input())
    for _ in range(tt):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
import sys

def solve(string, reps, idx, pos):
    if idx < 0:
        return string[pos - 1]
    (l, ls) = reps[idx]
    if pos < ls:
        return solve(string, reps, idx - 1, pos)
    else:
        return solve(string, reps, idx - 1, l + (pos - ls))
for i in range(int(next(sys.stdin).strip())):
    (n, c, q) = [int(x) for x in next(sys.stdin).strip().split()]
    string = next(sys.stdin).strip()
    repeats = []
    query = []
    for idx in range(c):
        (l, r) = [int(x) for x in next(sys.stdin).strip().split(' ')]
        repeats.append((l, n + 1))
        n = n + r - l + 1
    for idx in range(q):
        query = int(next(sys.stdin).strip())
        print(solve(string, repeats, c - 1, query))

Solution (Python):
from bisect import bisect_left
import sys
sys.setrecursionlimit(100000)
for item in range(int(input())):
    (n, c, q) = list((int(i) for i in sys.stdin.readline().split()))
    s = sys.stdin.readline().strip()
    intervals = []
    intervals = []
    intervals.append([1, n])
    lens = []
    lens.append(n)
    for j in range(c):
        (a, b) = list((int(i) for i in sys.stdin.readline().split()))
        intervals.append((a, b))
        lens.append(b - a + 1 + lens[-1])
    for j in range(q):
        x = int(sys.stdin.readline())
        ind = bisect_left(lens, x)
        while x > n:
            ind = bisect_left(lens, x)
            x = x - lens[ind - 1] - 1 + intervals[ind][0]
        print(s[x - 1])