← 返回题目列表

AtCoder · past23_k

K. 最常见的字符查询

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

问题陈述

给你一个字符串 S 长度 N,由小写英文字母组成。

处理给定的 Q 查询。有两种查询方式,如下所示:

  • 1 p c:设置 p- 第一个字符 S 到角色 c.
  • 2 l r:打印最常见的字母出现的次数 l-th 通过 r第一个字符 S.

约束

  • 1\le N\le 2\times 10^5
  • 1\le Q\le 2\times 10^5
  • S 是一个长度为的字符串 N,由小写英文字母组成。
  • 1\le p\le N
  • c 是一个小写英文字母。
  • 1\le l\le r\le N

输入

输入由标准输入按以下格式给出:

N Q
S
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

每个查询 \text{query}_Q 采用以下格式之一给出:

1 p c
2 l r

输出

打印对问题陈述中提出的查询的响应,以换行符分隔。


示例输入 1

6 4
abbabc
2 1 3
2 1 6
1 5 d
2 1 6

示例输出 1

2
3
2
  • 的 1-st 通过 3-rd 字符 S 是 abb。其中, b 出现最频繁,即 2 次。因此,打印 2 为 1-st 查询。
  • 的 1-st 通过 6第一个字符 S 是 abbabc。其中, b 出现最频繁,即 3 次。因此,打印 3 为 2-nd 查询。
  • 对于 3-rd查询,设置 5- 第一个字符 S to d, 制作 S= abbadc.
  • 的 1-st 通过 6第一个字符 S 是 abbadc。其中, a 和 b 出现最频繁,即 每个 2 次。因此,打印 2 为 4-第一个查询。

示例输入 2

8 4
nooutput
1 5 a
1 4 y
1 6 f
1 1 q

示例输出 2



示例输入 3

7 6
atcoder
2 1 7
1 1 r
2 1 7
1 2 r
2 1 7
1 4 r

示例输出 3

1
2
3