题解 CF1705C【Mark and His Unfinished Essay】
Anguei
2022-07-18 14:54:39
## 题意
给定一个字符串 $s_0$，以及 $c$ 次操作。第 $i$ 操作都会从上次操作得到的结果串中，选择 $s_{i-1_{[l, r]}}$ 范围内的子串，复制粘贴到上次结果串的末尾，得到一个新的串 $s_i$。经历完 $c$ 次操作之后，会得到一个最终串 $s_c$。
有 $q$ 次询问，每次询问指定一个位置 $x$，询问 $s_c$ 的第 $x$ 个字符是什么。
$n \leq 2 \times 10^5$，$c \leq 40$，$q \leq 1 \times 10^4$。
## 分析
第 $i$ 次操作的极限情况，是把 $s_{i-1}$ 完整的复制粘贴一遍。于是，$c$ 次操作之后，$s_c$ 的长度可高达 $n * 2^{40}$。故暴力模拟是不可行的。
记录下每次操作的：$l$，$r$，新生成的串的左右端点 $L$，以及 $R$。那么，每次操作，都会把上一个串的第 $r$ 个位置复制到新串的 $R$ 位置，$r-1$ 复制到 $R-1$ 的位置，以此类推，$l$ 复制到 $R - (r - l) = L$ 的位置。设 $d = R - r = L - l$，那么对于这次操作新生成的每一个位置 $x$，都与 $x - d$ 的位置上的字符相同。
以样例分析。第一组样例，一共有三次操作。原始串用原色表示，后面三个生成的串分别用红绿蓝表示。
| 1 | 2 | 3 | 4 | $\color{red}{\text{5}}$ | $\color{red}{\text{6}}$ | $\color{red}{\text{7}}$ | $\color{red}{\text{8}}$ | $\color{green}{\text{9}}$ | $\color{green}{\text{10}}$ | $\color{green}{\text{11}}$ | $\color{blue}{\text{12}}$ | $\color{blue}{\text{13}}$ | $\color{blue}{\text{14}}$ | $\color{blue}{\text{15}}$ | $\color{blue}{\text{16}}$ | $\color{blue}{\text{17}}$ |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| m | a | r | k | $\color{red}{\text{m}}$ | $\color{red}{\text{a}}$ | $\color{red}{\text{r}}$ | $\color{red}{\text{k}}$ | $\color{green}{\text{m}}$ | $\color{green}{\text{a}}$ | $\color{green}{\text{r}}$ | $\color{blue}{\text{r}}$ | $\color{blue}{\text{k}}$ | $\color{blue}{\text{m}}$ | $\color{blue}{\text{a}}$ | $\color{blue}{\text{r}}$ | $\color{blue}{\text{k}}$ |
1. 若询问最终串的第 $10$ 个字母，发现位置 $10$ 实在第二次操作（绿色部分）生成的，这次操作的 $d = 11 - 7 = 9 - 5 = 4$，所以第 $10$ 个字符就与第 $10-4=6$ 个字符相同。
2. 继续往前推，第 $6$ 个字符是在第一次操作（红色部分）生成的，这次操作的 $d = 4$，于是它又会与第 $6-4=2$ 个字符相等。
3. 第 $2$ 个字符，是在第零次操作中生成的，即属于原始字符串。直接输出 $s_2$ 即可。
就像这样从后往前跳，无论询问的坐标多大，一定会在 $c$ 次之内跳到原始串的范围当中。故总时间复杂度 $\mathcal{O}(qc)$。
## 代码
```cpp
struct OperationInfo {
ll l, r, L, R;
OperationInfo() {}
OperationInfo(ll l, ll r, ll L, ll R) : l(l), r(r), L(L), R(R) {}
};
void solution() {
int n, c, q;
read(n, c, q);
std::string s;
std::cin >> s;
s = " " + s;
std::vector<OperationInfo> oper(c + 1);
oper[0] = OperationInfo(0, 0, 1, n);
for (int i = 1; i <= c; ++i) {
read(oper[i].l, oper[i].r);
// 求出每次操作新生成的坐标范围
oper[i].L = oper[i - 1].R + 1;
oper[i].R = oper[i - 1].R + oper[i].r - oper[i].l + 1;
}
auto answer = [&]() {
ll pos;
read(pos);
for (int i = c; i >= 1; --i) {
if (pos >= oper[i].L) {
ll dis = oper[i].L - oper[i].l;
assert(dis == oper[i].R - oper[i].r);
pos -= dis;
}
}
std::cout << s[pos] << "\n";
};
for (int kase = 1; kase <= q; ++kase) answer();
}
```