P9482 [NOI2023] 字符串

小 Y 是一名大学生，最近正在研究字符串方向的问题。 小 Y 了解到关于字符串的如下定义: - 给定一个长度为 $n$ 的字符串 $s[1: n]$，我们定义其子串 $s[l: r]$（$1 \leq l \leq r \leq n$）为选择 $s[l], s[l+1], \dots, s[r]$, 将其顺次拼接得到的新字符串。 - 给定一个长度为 $n$ 的字符串 $s[1: n]$，我们定义其翻转后的结果 $R(s)$ 为将 $s[n], s[n-1], \dots, s[1]$ 顺次拼接，也就是将字符串反序拼接得到的字符串。 - 给定两个长度均为 $n$ 的字符串 $a[1: n], b[1: n]$，我们定义 $a$ 的字典序小于 $b$ 当且仅当存在 $1 \leq i \leq n$，使得对于任意 $1 \leq j < i$，$a[j] = b[j]$，且 $a[i] < b[i]$。 在了解了上述定义后，小 Y 想到了这样的问题: 给定一个长度为 $n$ 的字符串 $s[1: n]$。有 $q$ 次询问，每次询问给定两个参数 $i, r$。你需要求出有多少 $l$，满足如下条件: - $1 \leq l \leq r$。 - $s[i: i+l-1]$ 字典序小于 $R(s[i+l: i+2l-1])$。 小 Y 想求助你帮忙解决这一问题。

无

无

**【样例解释 #1】** 对于第一组数据的第一组询问： - $l = 1$ 时，$s[i: i + l - 1] = \texttt{a}$，$R(s[i + l: i + 2l - 1]) = \texttt{b}$。 - $l = 2$ 时，$s[i: i + l - 1] = \texttt{ab}$，$R(s[i + l: i + 2l - 1]) = \texttt{ca}$。 - $l = 3$ 时，$s[i: i + l - 1] = \texttt{aba}$，$R(s[i + l: i + 2l - 1]) = \texttt{bac}$。 - $l = 4$ 时，$s[i: i + l - 1] = \texttt{abac}$，$R(s[i + l: i + 2l - 1]) = \texttt{baba}$。 这四种情况中，$s[i: i + l - 1]$ 的字典序均小于 $R(s[i + l: i + 2l - 1])$。因此答案为 $4$。 **【样例解释 #2】** 该样例数据范围满足测试点 $5$。 **【样例解释 #4】** 该样例数据范围满足测试点 $24 \sim 25$。 **【数据范围】** 对于所有测试数据保证：$1 \le t \le 5$，$1 \le n \le 10 ^ 5$，$1 \le q \le 10 ^ 5$，$1 \le i + 2r - 1 \le n $，字符串 $s$ 仅包含小写字母。 |测试点编号|$n \le$|$q \le$|特殊性质| |:-:|:-:|:-:|:-:| |$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$|无| |$7$|$2,000$|$2,000$|无| |$8$|$3,000$|$3,000$|无| |$9$|$4,000$|$4,000$|无| |$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$|无| |$20$|$5 \times 10 ^ 4$|$5 \times 10 ^ 4$|无| |$21$|$75,000$|$75,000$|无| |$22$|$9 \times 10 ^ 4$|$9 \times 10 ^ 4$|无| |$23$|$95,000$|$95,000$|无| |$24 \sim 25$|$10 ^ 5$|$10 ^ 5$|无| 特殊性质 A：保证字符串中仅包含字符 $\texttt{a}$ 和 $\texttt{b}$，且每个字符独立等概率地在 $\texttt{a}$ 和 $\texttt{b}$ 中选择。 特殊性质 B：保证字符串中的相邻字符互不相同。