AT_abc415_f.[ABC415F] Max Combo

有一个长度为 $N$ 的仅由小写英文字母组成的字符串 $S$。请处理共 $Q$ 个如下的查询：

• 类型 $1$：将 $S$ 的第 $i$ 个字符修改为 $x$。
• 类型 $2$：取当前 $S$ 的第 $l$ 个字符到第 $r$ 个字符组成的子串 $t$。对于该字符串，求如下定义的 $f(t)$。
  • $f(t)$ 是 $t$ 中相同字符连续出现的最大长度。
  • 更严格地说，选择满足 $1\leq a\leq b\leq |t|$ 且 $t$ 的第 $a$ 个字符到第 $b$ 个字符全部相等的整数 $a,b$ 时，$f(t)$ 是所有 $b-a+1$ 的最大值。
  • 例如，$f($aaaccbbbb$)=4$，$f($bbaaabb$)=3$，$f($x$)=1$。

输入按以下格式从标准输入读入。

$N$ $Q$
$S$
$\rm{Query}_1$
$\rm{Query}_2$
$\vdots$
$\rm{Query}_Q$

其中，$\rm{Query}_i$ 表示第 $i$ 个查询。

类型 $1$ 的查询格式如下：

1 $i$ $x$

类型 $2$ 的查询格式如下：

2 $l$ $r$

每当出现类型 $2$ 的查询时，输出对应的答案，每个答案占一行。
注意，输入输出数据量可能较大，建议使用高效的输入输出方法。

限制条件

• $N$ 是 $1$ 到 $5\times 10^5$ 之间的整数。
• $S$ 是长度为 $N$ 的小写英文字母字符串。
• $Q$ 是 $1$ 到 $5\times 10^5$ 之间的整数。
• 类型 $1$ 查询满足以下限制：
  • $i$ 是 $1$ 到 $N$ 之间的整数。
  • $x$ 是小写英文字母。
• 类型 $2$ 查询满足以下限制：
  • $l,r$ 是满足 $1\leq l\leq r\leq N$ 的整数。

样例解释 1

本输入包含 $5$ 个查询。

• 初始字符串 $S$ 为 babaacczcc。
• 第 $1$ 个查询为类型 $2$，$l=1,r=4$。
• 取出的子串为 baba，$f($baba$)=1$。
• 第 $2$ 个查询为类型 $1$，$i=3,x=$a。
• 修改后字符串 $S=$baaaacczcc。
• 第 $3$ 个查询为类型 $2$，$l=1,r=10$。
• 取出的子串为 baaaacczcc，$f($baaaacczcc$)=4$。
• 第 $4$ 个查询为类型 $1$，$i=8,x=$c。
• 修改后字符串 $S=$baaaaccccc。
• 第 $5$ 个查询为类型 $2$，$l=1,r=10$。
• 取出的子串为 baaaaccccc，$f($baaaaccccc$)=5$。

样例解释 2

也有可能没有任何输出。

由 ChatGPT 4.1 翻译