P12490 [集训队互测 2024] 字符串

给定一个长度为 $n$ 的字符串 $s[1: n]$。有 $q$ 次询问，每次询问给定两个参数 $i, r$。你需要求出有多少 $l$，满足如下条件: - $1 \leq l \leq 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 \leq n$。

对于每一次询问，输出一行一个整数，表示满足条件的 $l$ 的个数。

### 数据范围 对于所有数据，$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%）：无特殊限制。