← 返回题目列表

Codeforces · 2209/E

E. 一个简单的字符串问题

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

将$$$f(t)$$$定义为$$$t$$$可以分割成的最大部分数,使得每个部分都是$$$t$$$的非空前缀。换句话说,$$$f(t)$$$是满足以下条件的最大正整数$$$k$$$:

  • 存在$$$k$$$字符串$$$p_1,p_2,\ldots,p_k$$$,它们是$$$t$$$的前缀,使得$$$t=p_1+p_2+\ldots+p_k$$$。这里$$$+$$$表示字符串连接。

给定一个字符串 $$$s$$$,长度为 $$$n$$$,仅包含小写英文字母。设 $$$s[x..y]$$$ 表示 $$$s$$$ 的子串 $$$^{\text{∗}}$$$ 从第 $$$x$$$ 到第 $$$y$$$ 个字符(含)。您需要回答 $$$q$$$ 查询。第 $$$i$$$ 查询提供了两个整数 $$$l_i$$$ 和 $$$r_i$$$,你需要找到

$$\sum_{j=l_i}^{r_i} f(s[l_i..j]).$$

$$$^{\text{*}}$$$ 字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le q \le 100$$$)。

第二行包含长度为$$$n$$$的字符串$$$s$$$,仅由小写英文字母组成。

接下来的 $$$q$$$ 行的第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$),表示第 $$$i$$$ 查询。

保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。

输出

对于每个查询,输出一个表示表达式值的整数。

示例

输入
复制

6
1 1
a
1 1
5 2
aaaaa
1 5
2 4
6 2
abcdef
1 6
3 5
6 3
abaaba
1 6
1 3
2 6
7 3
abcabca
1 7
2 7
4 7
8 3
aababaac
1 8
2 8
3 7

输出
复制

1
15
6
6
3
14
4
7
12
9
5
13
14
7

注意

在第一个测试用例中,$$$f(\texttt{a})=1$$$。

在第二个测试用例中, $$$f(\texttt{a})+f(\texttt{aa})+f(\texttt{aaa})+f(\texttt{aaaa})+f(\texttt{aaaaa})=1+2+3+4+5=15$$$ 并且$$$f(\texttt{a})+f(\texttt{aa})+f(\texttt{aaa})=1+2+3=6$$$。

在第三个测试用例中, $$$f(\texttt{a})+f(\texttt{ab})+f(\texttt{abc})+f(\texttt{abcd})+f(\texttt{abcde})+f(\texttt{abcdef})=1+1+1+1+1+1=6$$$ 和$$$f(\texttt{c})+f(\texttt{cd})+f(\texttt{cde})=1+1+1=3$$$。