题目背景

崩坏的句号

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$ 仅包含小写字母。