Logo Infinity Online Judge

InfOJ

时间限制:1 s 空间限制:512 MB

#274. [NOI2023] 字符串

Statistics

下发文件:http://119.27.163.117/download.php?type=problem&id=274

题目描述

小 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 想求助你帮忙解决这一问题。

输入格式

本题有多组测试数据。

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

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

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

输入的第二行包含一个长度为 $n$ 的仅包含小写字母的字符串 $s$。

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

4
0
3
2
0
2

样例 #2

样例输入 #2

见附件中的 string/string2.in。

样例输出 #2

见附件中的 string/string2.ans。

样例 #3

样例输入 #3

见附件中的 string/string3.in。

样例输出 #3

见附件中的 string/string3.ans。

样例 #4

样例输入 #4

见附件中的 string/string4.in。

样例输出 #4

见附件中的 string/string4.ans。

提示

【样例解释 #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:保证字符串中的相邻字符互不相同。