P9482 [NOI2023] String

Xiao Y is a college student who has recently been studying problems related to strings. Xiao Y learned the following definitions about strings: - Given a string $s[1: n]$ of length $n$, we define its substring $s[l: r]$ ($1 \leq l \leq r \leq n$) as the new string obtained by taking $s[l], s[l+1], \dots, s[r]$ and concatenating them in order. - Given a string $s[1: n]$ of length $n$, we define its reversed result $R(s)$ as the string obtained by concatenating $s[n], s[n-1], \dots, s[1]$ in order, i.e., reversing the string. - Given two strings $a[1: n], b[1: n]$ of length $n$, we say $a$ is lexicographically smaller than $b$ if and only if there exists $1 \leq i \leq n$ such that for all $1 \leq j < i$, $a[j] = b[j]$, and $a[i] < b[i]$. After understanding the definitions above, Xiao Y came up with the following problem: Given a string $s[1: n]$ of length $n$. There are $q$ queries, and each query gives two parameters $i, r$. You need to find how many $l$ satisfy the following conditions: - $1 \leq l \leq r$. - $s[i: i+l-1]$ is lexicographically smaller than $R(s[i+l: i+2l-1])$. Xiao Y asks you for help to solve this problem.

**This problem contains multiple test cases.** The first line of input contains two integers $c, t$, representing the test point ID and the number of test cases. $c=0$ means this test point is the sample. Then each test case is given as follows. For each test case: The first line contains two positive integers $n, q$, representing the string length and the number of queries. The second line contains a string $s$ of length $n$ consisting only of lowercase letters. The next $q$ lines each contain two positive integers $i, r$, representing one query. It is guaranteed that $i+2r-1 \leq n$.

For each query in each test case, output one line with an integer, representing the number of $l$ that satisfy the conditions.

**[Sample Explanation #1]** For the first query of the first test case: - When $l = 1$, $s[i: i + l - 1] = \texttt{a}$, and $R(s[i + l: i + 2l - 1]) = \texttt{b}$. - When $l = 2$, $s[i: i + l - 1] = \texttt{ab}$, and $R(s[i + l: i + 2l - 1]) = \texttt{ca}$. - When $l = 3$, $s[i: i + l - 1] = \texttt{aba}$, and $R(s[i + l: i + 2l - 1]) = \texttt{bac}$. - When $l = 4$, $s[i: i + l - 1] = \texttt{abac}$, and $R(s[i + l: i + 2l - 1]) = \texttt{baba}$. In all four cases, $s[i: i + l - 1]$ is lexicographically smaller than $R(s[i + l: i + 2l - 1])$. Therefore, the answer is $4$. **[Sample Explanation #2]** The Constraints of this sample satisfy test point $5$. **[Sample Explanation #4]** The Constraints of this sample satisfy test points $24 \sim 25$. **[Constraints]** For all testdata, it is guaranteed that: $1 \le t \le 5$, $1 \le n \le 10 ^ 5$, $1 \le q \le 10 ^ 5$, $1 \le i + 2r - 1 \le n $, and the string $s$ consists only of lowercase letters. |Test Point ID|$n \le$|$q \le$|Special Property| |:-:|:-:|:-:|:-:| |$1$|$5$|$5$|A| |$2$|$10$|$10$|A| |$3$|$20$|$20$|A| |$4$|$50$|$50$|A| |$5$|$10^2$|$10^2$|A| |$6$|$10^3$|$10^3$|None| |$7$|$2,000$|$2,000$|None| |$8$|$3,000$|$3,000$|None| |$9$|$4,000$|$4,000$|None| |$10$|$23,333$|$23,333$|A| |$11$|$5 \times 10 ^ 4$|$5 \times 10 ^ 4$|A| |$12$|$75,000$|$75,000$|A| |$13$|$9 \times 10 ^ 4$|$9 \times 10 ^ 4$|A| |$14$|$10 ^ 5$|$10 ^ 5$|A| |$15$|$23,333$|$23,333$|B| |$16$|$75,000$|$$75,000$|B| |$17$|$9 \times 10 ^ 4$|$9 \times 10 ^ 4$|B| |$18$|$10 ^ 5$|$10 ^ 5$|B| |$19$|$23,333$|$23,333$|None| |$20$|$5 \times 10 ^ 4$|$5 \times 10 ^ 4$|None| |$21$|$75,000$|$75,000$|None| |$22$|$9 \times 10 ^ 4$|$9 \times 10 ^ 4$|None| |$23$|$95,000$|$95,000$|None| |$24 \sim 25$|$10 ^ 5$|$10 ^ 5$|None| Special property A: It is guaranteed that the string contains only characters $\texttt{a}$ and $\texttt{b}$, and each character independently chooses between $\texttt{a}$ and $\texttt{b}$ with equal probability. Special property B: It is guaranteed that adjacent characters in the string are all different. **On Luogu, in this problem, Subtask 1 contains hack data, and it is guaranteed that $c=25$**. Translated by ChatGPT 5