← 返回题目列表

Codeforces · 1943/B

B. 非回文子串

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

如果存在至少一个长度为 $$$k$$$ 且不是回文 $$$^\ddagger$$$ 的子串 $$$^\dagger$$$,则称字符串 $$$t$$$ 是 $$$k$$$-好。让 $$$f(t)$$$ 表示 $$$k$$$ 的所有值的总和,使得字符串 $$$t$$$ 是 $$$k$$$-good。

给定一个长度为 $$$n$$$ 的字符串 $$$s$$$。您必须回答以下问题中的$$$q$$$:

- 给定 $$$l$$$ 和 $$$r$$$ ($$$l < r$$$),找到 $$$f(s_ls_{l + 1}\ldots s_r)$$$ 的值。

$$$^\dagger$$$ 字符串 $$$z$$$ 的子字符串是来自 $$$z$$$ 的连续字符段。例如,“$$$\mathtt{defor}$$$”、“$$$\mathtt{code}$$$”和“$$$\mathtt{o}$$$”都是“$$$\mathtt{codeforces}$$$”的子字符串,而“$$$\mathtt{codes}$$$”和“$$$\mathtt{aaa}$$$”是不。

$$$^\ddagger$$$ 回文是向后读取与向前读取相同的字符串。例如,字符串“$$$\texttt{z}$$$”、“$$$\texttt{aa}$$$”和“$$$\texttt{tacocat}$$$”是回文,而“$$$\texttt{codeforces}$$$”和“$$$\texttt{ab}$$$”不是回文。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5, 1 \le q \le 2 \cdot 10^5$$$),分别是字符串的大小和查询的数量。

每个测试用例的第二行包含字符串$$$s$$$。保证字符串 $$$s$$$ 仅包含小写英文字符。

接下来的 $$$q$$$ 行每行包含两个整数,$$$l$$$ 和 $$$r$$$ ($$$1 \le l < r \le n$$$)。

保证$$$n$$$之和与$$$q$$$之和不超过$$$2 \cdot 10^5$$$。

输出

对于每个查询,输出 $$$f(s_ls_{l + 1}\ldots s_r)$$$。

示例

输入 #1

5
4 4
aaab
1 4
1 3
3 4
2 4
3 2
abc
1 3
1 2
5 4
pqpcc
1 5
4 5
1 3
2 4
2 1
aa
1 2
12 1
steponnopets
1 12

输出 #1

9
0
2
5
5
2
14
0
2
5
0
65

注意

在第一个测试用例的第一个查询中,字符串为 $$$\mathtt{aaab}$$$。 $$$\mathtt{aaab}$$$、$$$\mathtt{aab}$$$ 和 $$$\mathtt{ab}$$$ 都是非回文子串,它们的长度分别为 $$$4$$$、$$$3$$$ 和 $$$2$$$。因此,字符串是 $$$2$$$-good、$$$3$$$-good 和 $$$4$$$-good。因此,$$$f(\mathtt{aaab}) = 2 + 3 + 4 = 9$$$。

在第一个测试用例的第二个查询中,字符串为 $$$\mathtt{aaa}$$$。不存在非回文子串。因此,$$$f(\mathtt{aaa}) = 0$$$。

在第二个测试用例的第一个查询中,字符串为 $$$\mathtt{abc}$$$。 $$$\mathtt{ab}$$$、$$$\mathtt{bc}$$$ 和 $$$\mathtt{abc}$$$ 都是非回文子串,它们的长度分别为 $$$2$$$、$$$2$$$ 和 $$$3$$$。因此,字符串是 $$$2$$$-good 和 $$$3$$$-good。因此,$$$f(\mathtt{abc}) = 2 + 3 = 5$$$。请注意,即使有 $$$2$$$ 长度为 $$$2$$$ 的非回文子串,我们也只计算一次。