P17704 [ICPC 2019 Nanjing R] Paper Grading

故事纯属虚构。 第 84 大学的几乎所有学生都被要求参加一门名为 JL 的必修课并通过考试，这意味着数百名学生将一起参加这场期末考试。组织这门课程的老师一直在努力寻找一种更高效、更公平的方式来评阅试卷。今年，你被任命编写一个程序来评阅试卷。 现在，你拿到了一本“规则手册”，它实际上是一本由 $n$ 个仅含小写字母的字符串组成的字典，依次记作 $s_1, s_2, \cdots, s_n$。然而，这本书作为一件魔法物品，可能会通过交换操作而被修改。可以随时交换字典中两个字符串的位置。例如，如果有人交换了第一个和第五个字符串，那么修改后这本字典中所谓的第一个字符串将是原来的第五个。 评分标准如下。一名学生及其试卷被描述为一个仅含小写字母的字符串 $q$ 以及三个整数系数 $k, l, r$。该学生的最终得分应为规则手册中满足 $l \le i \le r$ 且 $q$ 与 $s_i$ 的最长公共前缀长度至少为 $k$ 的字符串 $s_i$ 的个数。

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 2 \times 10^5$），其中 $n$ 是规则手册中字符串的个数，$m$ 是修改操作与学生查询的总次数。 接下来的 $n$ 行为 $n$ 个非空字符串 $s_1, s_2, \cdots, s_n$，表示手册中的所有字符串，它们的总长度不超过 $2 \times 10^5$。 再接下来的 $m$ 行，按时间顺序描述了所有修改操作和需要评分的学生的查询。每行以一个整数 $opt$（$1 \le opt \le 2$）开头。 - 若 $opt=1$，后跟两个整数 $i$ 和 $j$，描述了一次交换手册中第 $i$ 个和第 $j$ 个字符串的修改操作，其中 $1 \le i, j \le n$，$i$ 可以等于 $j$。 - 若 $opt=2$，后跟一个非空字符串 $q$ 以及三个非负整数 $k, l, r$，其中 $0 \le k \le |q|$ 且 $1 \le l \le r \le n$，表示如上所述的一名学生。 保证输入中给出的所有 $q$ 的总长度不超过 $2 \times 10^5$。

对于每名学生，输出一行一个整数，表示其试卷的得分。

在样例中，初始的规则手册由 $s_1 = \texttt{aaa}$、$s_2 = \texttt{bbb}$ 和 $s_3 = \texttt{aac}$ 组成。对于第一个给定的学生，其字符串 $q = \texttt{aasdd}$，它与 $\texttt{aaa}$ 和 $\texttt{aac}$ 的最长公共前缀长度均至少为 $2$，因此他的最终得分为 $2$。对于第二个学生，手册中唯一需要考虑的字符串是第一个 $s_1 = \texttt{aaa}$。 随后发生了一次修改，规则手册中的字符串变为 $s_1 = \texttt{aaa}$、$s_2 = \texttt{aac}$ 和 $s_3 = \texttt{bbb}$。对于第三个学生，$s_1$ 和 $s_2$ 与给定的 $q = \texttt{aat}$ 均拥有长度为 $2$ 的公共前缀，因此答案为 $2$。 翻译由 DeepSeek V4 Pro 完成