题解 CF1705C【Mark and His Unfinished Essay】

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)$。

代码

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();
}