CF862F Mahmoud and Ehab and the final stage

Mahmoud 和 Ehab 解答了 Dr. Evil 的问题，因此他给了他们通往邪恶之地大门的密码。当他们尝试使用密码打开大门时，大门又给了他们最后一道题（没错，大门是数字化的，Dr. Evil 很现代）。如果他们无法解开这道题，所有的努力都将白费，他们将永远无法离开邪恶之地。你愿意帮助他们吗？ Mahmoud 和 Ehab 得到了 $n$ 个字符串 $s_{1}, s_{2}, \ldots, s_{n}$，编号从 $1$ 到 $n$，同时还有 $q$ 个操作。每个操作有如下两种形式之一： - $1\ a\ b\ (1 \leq a \leq b \leq n)$，对于所有满足 $a \leq l \leq r \leq b$ 的区间 $[l, r]$，求下式的最大值：$(r-l+1) \times \operatorname{LCP}(s_{l}, s_{l+1}, \ldots, s_{r})$，其中 $\operatorname{LCP}(str_{1}, str_{2}, str_{3}, \ldots)$ 表示字符串 $str_{1}, str_{2}, str_{3}, \ldots$ 的最长公共前缀的长度。 - $2\ x\ y\ (1 \leq x \leq n)$，其中 $y$ 是一个仅由小写英文字母组成的字符串。将第 $x$ 个字符串替换为 $y$。

输入的第一行为两个整数 $n$ 和 $q$，即字符串个数与操作个数，满足 $1 \leq n \leq 10^{5}, 1 \leq q \leq 10^{5}$。 第二行为 $n$ 个仅由小写英文字母组成的字符串 $str_{i}$。 接下来的 $q$ 行描述了操作，每行有如下两种形式之一： - $1\ a\ b\ (1 \leq a \leq b \leq n)$ - $2\ x\ y\ (1 \leq x \leq n)$，其中 $y$ 是一个由小写英文字母组成的字符串。 所有输入字符串总长度不超过 $10^{5}$。

对于每一个第一种类型的操作，在新的一行输出对应的答案。

由 ChatGPT 5 翻译