CF1943B.Non-Palindromic Substring

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

给定一个长度为 $n$ 的字符串 $s$，你需要回答 $q$ 个如下的查询：

• 给定 $l$ 和 $r$（$l < r$），求 $f(s_ls_{l + 1}\ldots s_r)$ 的值。

$^\dagger$ 字符串 $z$ 的子串是 $z$ 中一段连续的字符。例如，"defor"、"code" 和 "o" 都是 "codeforces" 的子串，而 "codes" 和 "aaa" 不是。

$^\ddagger$ 回文串是指正着读和反着读都相同的字符串。例如，"z"、"aa" 和 "tacocat" 是回文串，而 "codeforces" 和 "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)$ 的值。

在第一个测试用例的第一个查询中，字符串为 $\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$ 的非回文子串有两个，但只计一次。

由 ChatGPT 4.1 翻译