Mark and His Unfinished Essay

题意翻译

给定长度为 $n$ 的字符串 $s$，进行 $c$ 次操作，每次操作将 $s_l$ 到 $s_r$ 复制到字符串尾。 全部操作结束后有 $q$ 次询问，每次询问字符串 $s$ 的第 $k$ 位。 $1≤n≤2⋅10^5,1\leq c\leq 40,1\leq q\leq 10^4,1≤l≤r≤10^{18},1≤k≤10^{18}$ 数据保证 $r$ 不超过当前字符串长度，$k$ 不超过最终字符串长度。 by Wu_while

题目描述

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

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

m
a
r
e
a
r

说明

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}} $ .

**题目大意**：

给定一个初始长度为 $ n $ 的字符串 $ s $，进行 $ c $ 次操作，每次操作将字符串 $ s $ 中从 $ s_l $ 到 $ s_r $ 的部分复制到字符串尾部。所有操作结束后，有 $ q $ 次询问，每次询问最终字符串 $ s $ 的第 $ k $ 位字符。

**输入输出数据格式**：

- **输入格式**：
- 第一行包含一个整数 $ t $（$ 1 \leq t \leq 1000 $），表示测试用例的数量。
- 每个测试用例的第一行包含三个整数 $ n $、$ c $ 和 $ q $（$ 1 \leq n \leq 2 \times 10^5 $，$ 1 \leq c \leq 40 $，$ 1 \leq q \leq 10^4 $），分别表示初始字符串 $ s $ 的长度、复制粘贴操作的数量和询问的数量。
- 每个测试用例的第二行包含一个长度为 $ n $ 的字符串 $ s $。保证 $ s $ 只包含小写英文字母。
- 接下来的 $ c $ 行描述复制粘贴操作。每行包含两个整数 $ l $ 和 $ r $（$ 1 \leq l \leq r \leq 10^{18} $）。保证 $ r $ 不超过当前字符串 $ s $ 的长度。
- 每个测试用例的最后 $ q $ 行描述询问。每行包含一个整数 $ k $（$ 1 \leq k \leq 10^{18} $）。保证 $ k $ 不超过最终字符串 $ s $ 的长度。
- 保证所有测试用例的 $ n $ 和 $ q $ 之和分别不超过 $ 2 \times 10^5 $ 和 $ 10^4 $。

- **输出格式**：
- 对于每个询问，输出最终字符串 $ s $ 的第 $ k $ 位字符。

**输入输出样例**：

- 输入样例 #1：
```
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
```
- 输出样例 #1：
```
m
a
r
e
a
r
```**题目大意**： 给定一个初始长度为 $ n $ 的字符串 $ s $，进行 $ c $ 次操作，每次操作将字符串 $ s $ 中从 $ s_l $ 到 $ s_r $ 的部分复制到字符串尾部。所有操作结束后，有 $ q $ 次询问，每次询问最终字符串 $ s $ 的第 $ k $ 位字符。 **输入输出数据格式**： - **输入格式**： - 第一行包含一个整数 $ t $（$ 1 \leq t \leq 1000 $），表示测试用例的数量。 - 每个测试用例的第一行包含三个整数 $ n $、$ c $ 和 $ q $（$ 1 \leq n \leq 2 \times 10^5 $，$ 1 \leq c \leq 40 $，$ 1 \leq q \leq 10^4 $），分别表示初始字符串 $ s $ 的长度、复制粘贴操作的数量和询问的数量。 - 每个测试用例的第二行包含一个长度为 $ n $ 的字符串 $ s $。保证 $ s $ 只包含小写英文字母。 - 接下来的 $ c $ 行描述复制粘贴操作。每行包含两个整数 $ l $ 和 $ r $（$ 1 \leq l \leq r \leq 10^{18} $）。保证 $ r $ 不超过当前字符串 $ s $ 的长度。 - 每个测试用例的最后 $ q $ 行描述询问。每行包含一个整数 $ k $（$ 1 \leq k \leq 10^{18} $）。保证 $ k $ 不超过最终字符串 $ s $ 的长度。 - 保证所有测试用例的 $ n $ 和 $ q $ 之和分别不超过 $ 2 \times 10^5 $ 和 $ 10^4 $。 - **输出格式**： - 对于每个询问，输出最终字符串 $ s $ 的第 $ k $ 位字符。 **输入输出样例**： - 输入样例 #1： ``` 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 ``` - 输出样例 #1： ``` m a r e a r ```