#6092. 「Codeforces Round #418」恋爱循环

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: cyand1317

题目描述

セーノ
预备、起

字符串 s 对于字符 c 的权值,定义为 s 中仅由 c 组成的最长连续子串的长度。例如,对于 s = \texttt{kooomio} ,其由字符 \texttt{o} 组成的最长连续子串为 \texttt{ooo} ,因此它对于字符 \texttt{o} 的权值为 3

给定由小写字母组成的字符串 s 以及 q 个询问。每个询问形如 (m_i, c_i) ,表示「求出在 s 至多更改 m_i 个位置的字符后所得的字符串 s' 对于字符 c_i 的最大权值」。

输入格式

输入的第一行包含一个正整数 n —— 字符串 s 的长度。

第二行包含 n 个小写英文字母组成的字符串 s_{1} s_2 \ldots s_n —— 给定的初始字符串。

第三行包含一个正整数 q —— 询问的数目。

接下来 q 行,每行包含一个正整数 m_i —— 至多在 s 中更改的字符数目,和以一个空格分隔的小写字母 m_i —— 计算权值时使用的字符。

输出格式

输出 q 行:对于每个询问输出一行,包含一个整数 —— 进行更改后所得字符串 s' 的最大权值。

样例

样例输入 1

6
koyomi
3
1 o
4 o
4 m

样例输出 1

3
6
5

样例解释 1

在样例 1 中,有三个询问:

  • 在第一个询问中,最多可以更改 s 一个位置上的字符,将 \texttt{y} 所处的位置改为 \texttt{o} 得到 s' = \texttt{kooomi} ,权值为 3
  • 在第二个询问中,最多可以更改 s 四个位置上的字符, s' = \texttt{oooooo} 的权值为 6
  • 在第三个询问中,最多可以更改 s 四个位置上的字符, s' = \texttt{mmmmmi} s' = \texttt{kmmmmm} 的权值均为 5

样例输入 2

15
yamatonadeshiko
10
1 a
2 a
3 a
4 a
5 a
1 b
2 b
3 b
4 b
5 b

样例输出 2

3
4
5
7
8
1
2
3
4
5

样例输入 3

10
aaaaaaaaaa
2
10 b
10 z

样例输出 3

10
10

数据范围与提示

1 \leq n \leq 1\,500
1 \leq q \leq 200\,000
1 \leq m_i \leq n c_i 为小写英文字母

コイスル キセツハ ヨクバリ サーキュレーション
恋爱的季节是激情洋溢的循环
コイスル キモチハ ヨクバリ サーキュレーション
恋爱的心情是激情洋溢的循环
            ——「恋愛サーキュレーション」