Preparing NOJ

攻防演练

1000ms 524288K

Description:

小Q和小C在比特公司的系统中进行攻防演练,这个系统经过特殊设定,只能接收任何只含有前 $$$m$$$ 个小写英文字母的非空字符串作为输入命令。

小Q事先准备了一个长为 $$$n$$$ 的字符串 $$$s = s_1 s_2 \ldots s_n$$$,为了能够在演练时输入到系统中,这个字符串只会包含前 $$$m$$$ 个小写英文字母。攻防演练一共进行 $$$q$$$ 轮,每轮开始时小Q会选择一个 $$$s$$$ 的非空子串 $$$s_{l,r} = s_l s_{l+1} \ldots s_r$$$ 输入到系统中作为本轮演练的防火墙规则。当防火墙规则配置完成之后,对于任何输入到系统中的命令 $$$c$$$,只要 $$$c$$$ 是 $$$s_{l,r}$$$ 的子序列就会被防火墙拦截。

小C的任务是在每轮演练中,在小Q完成本轮防火墙规则的配置之后,输入一个不被防火墙拦截的命令。为了节约时间,小C想知道每轮演练需要输入的最短字符串的长度是多少。也就是说,小C想找到最小的正整数 $$$k$$$,存在一个长为 $$$k$$$ 的字符串 $$$t = t_1 t_2 \ldots t_k$$$,使得不存在任意一个长为 $$$k$$$ 的序列 $$$p_1, p_2, \ldots p_k$$$ 满足 $$$l \le p_1 < p_2 < \ldots < p_k \le r$$$ 且对每个 $$$i=1,2,\ldots,k$$$ 均有 $$$t_i = s_{p_i}$$$。

Input:

第一行包含两个正整数 $$$m$$$ ($$$1 \le m \le 26$$$) 和 $$$n$$$ ($$$1 \le n \le 200\,000$$$),分别表示比特公司系统接受的命令的字符集大小和小Q事先准备的字符串的长度。

第二行包含一个长为 $$$n$$$ 的只包含前 $$$m$$$ 个小写英文字母的字符串,表示小Q事先准备的字符串。

第三行包含一个正整数 $$$q$$$ ($$$1 \le q \le 200\,000$$$),表示攻防演练进行的轮数。

接下来 $$$q$$$ 行,每行包含两个正整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$),表示本轮攻防演练中小Q配置字符串 $$$s_{l,r}$$$ 为防火墙规则。

Output:

输出 $$$q$$$ 行,每行包含一个正整数,表示本轮攻防演练中小C为了达成目标所需要输入的最短字符串的长度。

Sample Input:

2 6
abaabb
3
1 4
2 5
3 6

Sample Output:

2
3
2

Info

CodeForces Gym

Provider CodeForces Gym

Origin 2021年中国大学生程序设计竞赛女生专场

Code GYM103389B

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 11/01/2021 22:24:16

Related

Nothing Yet