3856. [USACO23 Jan Gold] Find and Replace

【题目描述】

给定一个字符串 $"a"$，你需要对其进行 $q$ 次操作。

每次操作给定一个小写字母 $c$ 和一个由小写字母构成的非空字符串 $s$，你需要将当前字符串中出现的所有 $c$ 替换为 $s$。

例如，如果当前字符串为 $ball$，$c$ 为 $l$，$s$ 为 $na$，则操作过后，当前字符串变为 $banana$。

当所有操作都完成后，我们可以得到一个最终字符串 $S$。

给定 $l,r$，请你输出 $S_{l \cdots r}$（$S$ 的第 $l$ 个字符到第 $r$ 个字符构成的子串）。

$S$ 的字符下标从左到右，依次为 $1,2,\cdots,|S|$。

【输入格式】

第一行包含三个整数 $l,r,q$。

接下来 $q$ 行，每行包含一个小写字母 $c$ 和一个由小写字母构成的非空字符串 $s$，表示一次替换操作。

【输出格式】

输出 $S_{l \cdots r}$。

【样例1输入】

3 8 4
a ab
a bc
c de
b bbb

【样例1输出】

bdebbb

【样例1解释】

字符串变化如下：$a\ →\ ab\ →\ bcb\ →\ bdeb\ →\ bbbdebbb$

【样例2】

点击下载样例2

【数据规模与约定】

测试点 $2 \sim 7$：$∑|s|,r−l+1≤2000$；

对于 $100\%$ 的数据，$1≤l≤r≤min(|S|,10^{18})，1≤q≤2×10^5$，

$∑∣s∣≤2×10^5，r−l+1 ≤ 2×10^5$。