#P12686. [集训队互测2025day13]字符串

    ID: 11872 传统题 2000ms 1024MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-后缀数组Kasai 算法LCP+RMQST 表串联重复Main–Lorentz 算法分治算法离线查询查询排序树状数组差分树状数组

[集训队互测2025day13]字符串

题目描述

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

  • 1≤l≤r1 \leq l \leq r。
  • s[i:i+l−1]s[i: i+l-1] 字典序小于 s[i+l:i+2l−1]s[i+l: i+2l-1] 。

输入格式

第一行包含一个整数 cc,表示子任务编号。c=0c=0 表示该测试点为样例。

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

第三行包含一个长度为 nn 的仅包含小写字母的字符串 ss。

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

输出格式

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

输入输出样例 #1

输入 #1

0
9 3
abacababa
1 4
2 4
3 3

输出 #1

3
1
2

说明/提示

数据范围

对于所有数据,1≤n,q≤5×1051 \le n,q\le 5\times 10^5,1≤i+2r−1≤n1 \le i + 2r - 1 \le n ,字符串 ss 仅包含小写字母。

子任务 1(20%):n,q≤5×103n,q\le 5\times 10^3 。

子任务 2(10%):n,q≤105n,q\le 10^5 ,保证 ss 中每个字符在 a,b 中随机生成。

子任务 3(20%):n,q≤105n,q\le 10^5 。

子任务 4(20%):n,q≤3×105n,q\le 3\times 10^5 。

子任务 5(30%):无特殊限制。