Codeforces Round 934 (Div. 1) |
---|
Finished |
A string $$$t$$$ is said to be $$$k$$$-good if there exists at least one substring$$$^\dagger$$$ of length $$$k$$$ which is not a palindrome$$$^\ddagger$$$. Let $$$f(t)$$$ denote the sum of all values of $$$k$$$ such that the string $$$t$$$ is $$$k$$$-good.
You are given a string $$$s$$$ of length $$$n$$$. You will have to answer $$$q$$$ of the following queries:
$$$^\dagger$$$ A substring of a string $$$z$$$ is a contiguous segment of characters from $$$z$$$. For example, "$$$\mathtt{defor}$$$", "$$$\mathtt{code}$$$" and "$$$\mathtt{o}$$$" are all substrings of "$$$\mathtt{codeforces}$$$" while "$$$\mathtt{codes}$$$" and "$$$\mathtt{aaa}$$$" are not.
$$$^\ddagger$$$ A palindrome is a string that reads the same backwards as forwards. For example, the strings "$$$\texttt{z}$$$", "$$$\texttt{aa}$$$" and "$$$\texttt{tacocat}$$$" are palindromes while "$$$\texttt{codeforces}$$$" and "$$$\texttt{ab}$$$" are not.
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5, 1 \le q \le 2 \cdot 10^5$$$), the size of the string and the number of queries respectively.
The second line of each test case contains the string $$$s$$$. It is guaranteed the string $$$s$$$ only contains lowercase English characters.
The next $$$q$$$ lines each contain two integers, $$$l$$$ and $$$r$$$ ($$$1 \le l < r \le n$$$).
It is guaranteed the sum of $$$n$$$ and the sum of $$$q$$$ both do not exceed $$$2 \cdot 10^5$$$.
For each query, output $$$f(s_ls_{l + 1}\ldots s_r)$$$.
54 4aaab1 41 33 42 43 2abc1 31 25 4pqpcc1 54 51 32 42 1aa1 212 1steponnopets1 12
9 0 2 5 5 2 14 0 2 5 0 65
In the first query of the first test case, the string is $$$\mathtt{aaab}$$$. $$$\mathtt{aaab}$$$, $$$\mathtt{aab}$$$ and $$$\mathtt{ab}$$$ are all substrings that are not palindromes, and they have lengths $$$4$$$, $$$3$$$ and $$$2$$$ respectively. Thus, the string is $$$2$$$-good, $$$3$$$-good and $$$4$$$-good. Hence, $$$f(\mathtt{aaab}) = 2 + 3 + 4 = 9$$$.
In the second query of the first test case, the string is $$$\mathtt{aaa}$$$. There are no non-palindromic substrings. Hence, $$$f(\mathtt{aaa}) = 0$$$.
In the first query of the second test case, the string is $$$\mathtt{abc}$$$. $$$\mathtt{ab}$$$, $$$\mathtt{bc}$$$ and $$$\mathtt{abc}$$$ are all substrings that are not palindromes, and they have lengths $$$2$$$, $$$2$$$ and $$$3$$$ respectively. Thus, the string is $$$2$$$-good and $$$3$$$-good. Hence, $$$f(\mathtt{abc}) = 2 + 3 = 5$$$. Note that even though there are $$$2$$$ non-palindromic substrings of length $$$2$$$, we count it only once.
Name |
---|