分数: 525 点
问题陈述
有一个字符串 S 长度 N 由小写英文字母组成。总共处理了 Q 查询如下:
- 类型 1 :更改 i- 第一个字符 S to x.
- 类型 2 :让 t 是当前的子字符串 S 来自 l- 第一个字符 r- 第一个字符。查找 f(t) 对此字符串定义如下:
- f(t) 是连续相同字符的最大长度 t.
- 更准确地说,选择整数时 a,b 这样 1 \le a \le b \le |t| 以及来自 a-th 通过 b- 第一个字符 t 相等, f(t) 是最大可能值 b-a+1.
- 例如, f(
aaaccbbbb)=4, f(bbaaabb)=3, f(x)=1.
约束
- N 是介于 1 和 5 \times 10^5,包括在内。
- S 是一个长度为的字符串 N 由小写英文字母组成。
- Q 是介于 1 和 5 \times 10^5,包括在内。
- 类型 1 查询满足以下约束:
- i 是介于 1 和 N,包括在内。
- x 是一个小写英文字母。
- 类型 2 查询满足以下约束:
- l,r 是满足以下条件的整数 1 \le l \le r \le N.
输入
输入由标准输入按以下格式给出:
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 查询,将答案输出一行。
由于潜在的大量输入和输出,建议使用快速输入和输出方法。
样本输入 1
10 5 babaacczcc 2 1 4 1 3 a 2 1 10 1 8 c 2 1 10
示例输出 1
1 4 5
此输入包含五个查询。
- 最初,字符串 S is
babaacczcc. - 的 1st 查询类型 2 与 l=1,r=4.
- 提取的字符串是
baba,和 f(baba)=1.
- 提取的字符串是
- 的 2nd 查询是类型 1 与 i=3,x=
a.- 字符串 S 更改后为
baaaacczcc.
- 字符串 S 更改后为
- 的 3rd 查询类型 2 与 l=1,r=10.
- 提取的字符串是
baaaacczcc,和 f(baaaacczcc)=4.
- 提取的字符串是
- 的 4第一个查询是类型 1 与 i=8,x=
c.- 字符串 S 更改后为
baaaaccccc.
- 字符串 S 更改后为
- 的 5第一个查询是类型 2 与 l=1,r=10.
- 提取的字符串是
baaaaccccc,和 f(baaaaccccc)=5.
- 提取的字符串是
示例输入 2
1 1 a 1 1 z
示例输出 2
输出可能为空。