Find and Replace

题目描述

Bessie 正在使用最新最强的文本编辑软件 miV！它强大的查找并替换功能允许她找到某个小写英文字母 $c$ 的所有出现位置，并将每一次出现都替换为一个非空的小写字母字符串 $s$。例如，给定字符串 "$\texttt{ball}$"，如果 Bessie 选择 $c$ 为 'l'，$s$ 为 "$\texttt{na}$"，则该字符串会变为 "$\texttt{banana}$"。 Bessie 从字符串 "$\texttt{a}$" 开始，通过若干次这样的查找并替换操作进行变换，最终得到字符串 $S$。由于 $S$ 可能非常庞大，她想知道：给定 $l$ 和 $r$，满足 $1\le l\le r\le \min(|S|,10^{18})$，子串 $S_{l\dots r}$（即 $S$ 中从第 $l$ 个字符到第 $r$ 个字符（含）组成的子串）是什么。 保证所有操作中 $|s|$ 的总和最多为 $2\cdot 10^5$，并且 $r-l+1\le 2\cdot 10^5$。

输入格式

第一行包含 $l$、$r$ 和操作次数。 接下来的每一行描述一个操作，包含该操作的 $c$ 和 $s$。 所有字符都在 'a' 到 'z' 的范围内。

输出格式

在一行中输出字符串 $S_{l\dots r}$。

4
abc
abc
BBC
ABC
abc
bbc
ABCD
BACD

0
-1
1
3

提示

样例解释：

• 第一个输入串与输出串相同，无需按键。
• 第二个输入串无法变换成输出串：Bessie 无法把一个 B 改成 A 而保持另一个仍是 B。
• 第三个输入串只需把 a 改成 b 即可变成输出串。
• 第四个输入串的变换过程：$\texttt{ABCD} \rightarrow \texttt{EBCD} \rightarrow \texttt{EACD} \rightarrow \texttt{BACD}$。

子任务：

• 测试点 2-6：所有字符串长度不超过 $50$。
• 测试点 7-9：所有字符串只含小写字母 a 到 e。
• 测试点 10-15：没有额外限制。

标签: USACO|2023|Gold

来源

USACO|2023|Gold