{"problem":{"name":"[NOI2023] 字符串","description":{"content":"小 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]$，我们定","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9482"},"statements":[{"statement_type":"Markdown","content":"小 Y 是一名大学生，最近正在研究字符串方向的问题。\n\n小 Y 了解到关于字符串的如下定义:\n\n- 给定一个长度为 $n$ 的字符串 $s[1: n]$，我们定义其子串 $s[l: r]$（$1 \\leq l \\leq r \\leq n$）为选择 $s[l], s[l+1], \\dots, s[r]$, 将其顺次拼接得到的新字符串。\n- 给定一个长度为 $n$ 的字符串 $s[1: n]$，我们定义其翻转后的结果 $R(s)$ 为将 $s[n], s[n-1], \\dots, s[1]$ 顺次拼接，也就是将字符串反序拼接得到的字符串。\n- 给定两个长度均为 $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]$。\n\n在了解了上述定义后，小 Y 想到了这样的问题:\n\n给定一个长度为 $n$ 的字符串 $s[1: n]$。有 $q$ 次询问，每次询问给定两个参数 $i, r$。你需要求出有多少 $l$，满足如下条件:\n- $1 \\leq l \\leq r$。\n- $s[i: i+l-1]$ 字典序小于 $R(s[i+l: i+2l-1])$。\n\n小 Y 想求助你帮忙解决这一问题。\n\n## Input\n\n**本题有多组测试数据。**\n\n输入的第一行包含两个整数 $c, t$，分别表示测试点编号和测试数据组数。$c=0$ 表示该测试点为样例。\n\n接下来依次输入每组测试数据，对于每组测试数据：\n\n输入的第一行包含两个正整数 $n, q$，表示字符串长度和询问次数。\n\n输入的第二行包含一个长度为 $n$ 的仅包含小写字母的字符串 $s$。\n\n输入的接下来 $q$ 行，每行包含两个正整数 $i, r$。表示一次询问，保证 $i+2r-1 \\leq n$。\n\n## Output\n\n对于每一组测试数据的每一次询问，输出一行一个整数，表示满足条件的 $l$ 的个数。\n\n[samples]\n\n## Note\n\n**【样例解释 #1】**\n\n对于第一组数据的第一组询问：\n- $l = 1$ 时，$s[i: i + l - 1] = \\texttt{a}$，$R(s[i + l: i + 2l - 1]) = \\texttt{b}$。\n- $l = 2$ 时，$s[i: i + l - 1] = \\texttt{ab}$，$R(s[i + l: i + 2l - 1]) = \\texttt{ca}$。\n- $l = 3$ 时，$s[i: i + l - 1] = \\texttt{aba}$，$R(s[i + l: i + 2l - 1]) = \\texttt{bac}$。\n- $l = 4$ 时，$s[i: i + l - 1] = \\texttt{abac}$，$R(s[i + l: i + 2l - 1]) = \\texttt{baba}$。\n\n这四种情况中，$s[i: i + l - 1]$ 的字典序均小于 $R(s[i + l: i + 2l - 1])$。因此答案为 $4$。\n\n**【样例解释 #2】**\n\n该样例数据范围满足测试点 $5$。\n\n**【样例解释 #4】**\n\n该样例数据范围满足测试点 $24 \\sim 25$。\n\n**【数据范围】**\n\n对于所有测试数据保证：$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\n|测试点编号|$n \\le$|$q \\le$|特殊性质|\n|:-:|:-:|:-:|:-:|\n|$1$|$5$|$5$|A|\n|$2$|$10$|$10$|A|\n|$3$|$20$|$20$|A|\n|$4$|$50$|$50$|A|\n|$5$|$10^2$|$10^2$|A|\n|$6$|$10^3$|$10^3$|无|\n|$7$|$2,000$|$2,000$|无|\n|$8$|$3,000$|$3,000$|无|\n|$9$|$4,000$|$4,000$|无|\n|$10$|$23,333$|$23,333$|A|\n|$11$|$5 \\times 10 ^ 4$|$5 \\times 10 ^ 4$|A|\n|$12$|$75,000$|$75,000$|A|\n|$13$|$9 \\times 10 ^ 4$|$9 \\times 10 ^ 4$|A|\n|$14$|$10 ^ 5$|$10 ^ 5$|A|\n|$15$|$23,333$|$23,333$|B|\n|$16$|$75,000$|$75,000$|B|\n|$17$|$9 \\times 10 ^ 4$|$9 \\times 10 ^ 4$|B|\n|$18$|$10 ^ 5$|$10 ^ 5$|B|\n|$19$|$23,333$|$23,333$|无|\n|$20$|$5 \\times 10 ^ 4$|$5 \\times 10 ^ 4$|无|\n|$21$|$75,000$|$75,000$|无|\n|$22$|$9 \\times 10 ^ 4$|$9 \\times 10 ^ 4$|无|\n|$23$|$95,000$|$95,000$|无|\n|$24 \\sim 25$|$10 ^ 5$|$10 ^ 5$|无|\n\n特殊性质 A：保证字符串中仅包含字符 $\\texttt{a}$ 和 $\\texttt{b}$，且每个字符独立等概率地在 $\\texttt{a}$ 和 $\\texttt{b}$ 中选择。\n\n特殊性质 B：保证字符串中的相邻字符互不相同。\n\n**在洛谷上，本题 Subtask 1 中为 hack 数据，保证 $c=25$**。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9482","tags":["字符串","树状数组","2023","NOI","O2优化","哈希 hashing","后缀数组 SA","Manacher 算法","bitset"],"sample_group":[["0 2\n9 3\nabacababa\n1 4\n2 4\n3 3\n9 3\nabaabaaba\n1 4\n2 4\n3 3\n","4\n0\n3\n2\n0\n2\n"],["见附件中的 string/string2.in。","见附件中的 string/string2.ans。"],["见附件中的 string/string3.in。","见附件中的 string/string3.ans。"],["见附件中的 string/string4.in。","见附件中的 string/string4.ans。"]],"created_at":"2026-03-03 11:09:25"}}