#P9482. [NOI2023] 字符串

[NOI2023] 字符串

题目描述

小 Y 是一名大学生,最近正在研究字符串方向的问题。

小 Y 了解到关于字符串的如下定义:

  • 给定一个长度为 nn 的字符串 s[1:n]s[1: n],我们定义其子串 s[l:r]s[l: r]1lrn1 \leq l \leq r \leq n)为选择 s[l],s[l+1],,s[r]s[l], s[l+1], \dots, s[r], 将其顺次拼接得到的新字符串。
  • 给定一个长度为 nn 的字符串 s[1:n]s[1: n],我们定义其翻转后的结果 R(s)R(s) 为将 s[n],s[n1],,s[1]s[n], s[n-1], \dots, s[1] 顺次拼接,也就是将字符串反序拼接得到的字符串。
  • 给定两个长度均为 nn 的字符串 a[1:n],b[1:n]a[1: n], b[1: n],我们定义 aa 的字典序小于 bb 当且仅当存在 1in1 \leq i \leq n,使得对于任意 1j<i1 \leq j < ia[j]=b[j]a[j] = b[j],且 a[i]<b[i]a[i] < b[i]

在了解了上述定义后,小 Y 想到了这样的问题:

给定一个长度为 nn 的字符串 s[1:n]s[1: n]。有 qq 次询问,每次询问给定两个参数 i,ri, r。你需要求出有多少 ll,满足如下条件:

  • 1lr1 \leq l \leq r
  • s[i:i+l1]s[i: i+l-1] 字典序小于 R(s[i+l:i+2l1])R(s[i+l: i+2l-1])

小 Y 想求助你帮忙解决这一问题。

输入格式

本题有多组测试数据。

输入的第一行包含两个整数 c,tc, t,分别表示测试点编号和测试数据组数。c=0c=0 表示该测试点为样例。

接下来依次输入每组测试数据,对于每组测试数据:

输入的第一行包含两个正整数 n,qn, q,表示字符串长度和询问次数。

输入的第二行包含一个长度为 nn 的仅包含小写字母的字符串 ss

输入的接下来 qq 行,每行包含两个正整数 i,ri, r。表示一次询问,保证 i+2r1ni+2r-1 \leq n

输出格式

对于每一组测试数据的每一次询问,输出一行一个整数,表示满足条件的 ll 的个数。

0 2
9 3
abacababa
1 4
2 4
3 3
9 3
abaabaaba
1 4
2 4
3 3

4
0
3
2
0
2

见附件中的 string/string2.in。
见附件中的 string/string2.ans。
见附件中的 string/string3.in。
见附件中的 string/string3.ans。
见附件中的 string/string4.in。
见附件中的 string/string4.ans。

提示

【样例解释 #1】

对于第一组数据的第一组询问:

  • l=1l = 1 时,s[i:i+l1]=as[i: i + l - 1] = \texttt{a}R(s[i+l:i+2l1])=bR(s[i + l: i + 2l - 1]) = \texttt{b}
  • l=2l = 2 时,s[i:i+l1]=abs[i: i + l - 1] = \texttt{ab}R(s[i+l:i+2l1])=caR(s[i + l: i + 2l - 1]) = \texttt{ca}
  • l=3l = 3 时,s[i:i+l1]=abas[i: i + l - 1] = \texttt{aba}R(s[i+l:i+2l1])=bacR(s[i + l: i + 2l - 1]) = \texttt{bac}
  • l=4l = 4 时,s[i:i+l1]=abacs[i: i + l - 1] = \texttt{abac}R(s[i+l:i+2l1])=babaR(s[i + l: i + 2l - 1]) = \texttt{baba}

这四种情况中,s[i:i+l1]s[i: i + l - 1] 的字典序均小于 R(s[i+l:i+2l1])R(s[i + l: i + 2l - 1])。因此答案为 44

【样例解释 #2】

该样例数据范围满足测试点 55

【样例解释 #4】

该样例数据范围满足测试点 242524 \sim 25

【数据范围】

对于所有测试数据保证:1t51 \le t \le 51n1051 \le n \le 10 ^ 51q1051 \le q \le 10 ^ 51i+2r1n1 \le i + 2r - 1 \le n ,字符串 ss 仅包含小写字母。

测试点编号 nn \le qq \le 特殊性质
11 55 A
22 1010
33 2020
44 5050
55 10210^2
66 10310^3
77 2,0002,000
88 3,0003,000
99 4,0004,000
1010 23,33323,333 A
1111 5×1045 \times 10 ^ 4
1212 75,00075,000
1313 9×1049 \times 10 ^ 4
1414 10510 ^ 5
1515 23,33323,333 B
1616 75,00075,000
1717 9×1049 \times 10 ^ 4
1818 10510 ^ 5
1919 23,33323,333
2020 5×1045 \times 10 ^ 4
2121 75,00075,000
2222 9×1049 \times 10 ^ 4
2323 95,00095,000
242524 \sim 25 10510 ^ 5

特殊性质 A:保证字符串中仅包含字符 a\texttt{a}b\texttt{b},且每个字符独立等概率地在 a\texttt{a}b\texttt{b} 中选择。

特殊性质 B:保证字符串中的相邻字符互不相同。