题目背景
崩坏的句号
trade 100 string 0 book 0
好丢人啊
s t r i n g 0 s t r i n g 0 s t r i n g 0 s t r i n g 0 s t r i n g 0 s t r i
只剩最后一次机会
$R(s[i+l:i+2l-1])$ $R(s[i+l:i+2l-1])$ $R(s[i+l:i+2l-1])$ $R(s[i+l:i+2l-1])$ $R(s[i+l$ $R$ $R$ $R$ $R$ $r$ $r$ $r$ $r$
不能再浪费了
2023.7
题目描述
给定一个长度为 $n$ 的字符串 $s[1:n]$。有 $q$ 次询问，每次询问给定两个参数 $i, r$。你需要求出有多少 $l$，满足如下条件:
- $1 \le l \le r$。
- $s[i:i+l-1]$ 字典序小于 $s[i+l:i+2l-1]$ 。
输入格式
第一行包含一个整数 $c$，表示子任务编号。$c=0$ 表示该测试点为样例。
第二行包含两个正整数 $n, q$，表示字符串长度和询问次数。
第三行包含一个长度为 $n$ 的仅包含小写字母的字符串 $s$。
接下来 $q$ 行，每行包含两个正整数 $i, r$，表示一次询问，保证 $i + 2r - 1 \le n$。
输出格式
对于每一次询问，输出一行一个整数，表示满足条件的 $l$ 的个数。
样例
样例输入 1
0 9 3 abacababa 1 4 2 4 3 3
样例输出 1
3 1 2
数据范围
对于所有数据，$1 \le n, q \le 5 \times 10^5$，$1 \le i + 2r - 1 \le n$，字符串 $s$ 仅包含小写字母。
| 子任务编号 | 分值 | 特殊性质 |
|---|---|---|
| $1$ | $20$ | $n, q \le 5 \times 10^3$ |
| $2$ | $10$ | $n, q \le 10^5$ ，保证 $s$ 中每个字符在 $a, b$ 中随机生成 |
| $3$ | $20$ | $n, q \le 10^5$ |
| $4$ | $20$ | $n, q \le 3 \times 10^5$ |
| $5$ | $30$ | 无特殊限制 |