CF610E Alphabet Permutations

给定一个长度为 $n$ 的字符串 $s$，该字符串由前 $k$ 个英文小写字母组成。 我们定义某个字符串 $q$ 的 $c$ 重复串为：由 $c$ 个 $q$ 串首尾相接组成的新字符串。例如，字符串 "acbacbacbacb" 是字符串 "acb" 的 $4$ 重复串。 如果字符串 $a$ 通过删除某些字符可以得到字符串 $b$，那么我们说 $a$ 包含 $b$ 作为子序列。 给定一个字符串 $p$，它是前 $k$ 个英文小写字母的某种排列。我们定义函数 $d(p)$ 表示：使得字符串 $p$ 的 $d(p)$ 重复串包含字符串 $s$ 作为子序列的最小整数。 现有 $m$ 个操作，对字符串 $s$ 依次进行，操作类型分为两种： 1. 将 $l_i$ 到 $r_i$ 的所有字符替换为字母 $c_i$。 2. 给定一个 $p$（为前 $k$ 个小写字母的某种排列），询问函数 $d(p)$ 的值。 所有操作按输入顺序依次进行。你的任务是对于所有第 2 种操作，依次输出相应的 $d(p)$。

第一行包含三个正整数 $n$、$m$ 和 $k$，表示字符串 $s$ 的长度、操作次数和字母表大小（$1 \le n \le 200000, 1 \le m \le 20000, 1 \le k \le 10$）。第二行是字符串 $s$。 接下来的 $m$ 行，每行一个操作描述： 1. 若为第一种操作，格式为 $1\ l_i\ r_i\ c_i$，表示将 $l_i$ 到 $r_i$（$1 \le l_i \le r_i \le n$）的位置都替换成字符 $c_i$（$c_i$ 是前 $k$ 个小写字母中的一个）。 2. 若为第二种操作，格式为 $2$ 和一个长度为 $k$ 的字符串 $p$，表示给出 $p$ 是前 $k$ 个字母的排列。

对于每个第 2 种操作，输出函数 $d(p)$ 的值。

第一次操作后，字符串 $s$ 变为 abbbbba。 第二次操作的答案是 $6$ 重复串 abc：ABcaBcaBcaBcaBcAbc。 第三次操作后，字符串 $s$ 变为 abbcbba。 第四次操作的答案是 $5$ 重复串 cba：cbAcBacBaCBacBA。 大写字母表示 $s$ 中字符的出现位置。 由 ChatGPT 5 翻译