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

「Codeforces Round #418」恋爱循环

题目描述

セーノ
预备、起

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

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

输入格式

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

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

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

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

输出格式

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

样例 1

6
koyomi
3
1 o
4 o
4 m
3
6
5

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

  • 在第一个询问中,最多可以更改 ss 一个位置上的字符,将 y\texttt{y} 所处的位置改为 o\texttt{o} 得到 s=kooomis' = \texttt{kooomi},权值为 33
  • 在第二个询问中,最多可以更改 ss 四个位置上的字符,s=oooooos' = \texttt{oooooo} 的权值为 66
  • 在第三个询问中,最多可以更改 ss 四个位置上的字符,s=mmmmmis' = \texttt{mmmmmi}s=kmmmmms' = \texttt{kmmmmm} 的权值均为 55
15
yamatonadeshiko
10
1 a
2 a
3 a
4 a
5 a
1 b
2 b
3 b
4 b
5 b
3
4
5
7
8
1
2
3
4
5
10
aaaaaaaaaa
2
10 b
10 z
10
10

数据范围与提示

1n15001 \leq n \leq 1\,500
1q2000001 \leq q \leq 200\,000
1min1 \leq m_i \leq ncic_i 为小写英文字母

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