← 返回题目列表

AtCoder · abc415_f

I. 最大组合

中文机器翻译题面 查看原题

分数: 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.
  • 的 3rd 查询类型 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

1 1
a
1 1 z

示例输出 2


输出可能为空。