串
给定一个由小写字母组成的字符串 a。
回答 q 次询问,每次询问给定一个 a 的子串 a[li,ri],求有多少个字符串 s 满足 s 是 a 的子串,且 s∞ 的字典序小于 a[li,ri]∞。
对于一个字符串 t,我们用 t∞ 表示 t 不断重复得到的无穷字符串。
输入格式
输入的第一行包含一个只包含小写字母的字符串 a 。
输入的第二行包含一个正整数 q 和一个整数 type,其中 type 表示数据类型。
接下来 q 行,第 i 行包含两个整数 li 和 ri。
输出格式
输出 q 行,每行一个整数表示一个询问的答案。
样例输入与输出
abbab
5 0
1 3
2 4
3 5
1 4
2 5
4
7
6
2
8
样例解释
询问 1 对应的子串是 abb,满足条件的子串有 a,ab,abba,abbab 共 4 个。
数据范围与子任务
对于所有数据,满足 1≤li≤ri≤∣a∣≤5×105,1≤q≤5×105。
下表中数据类型 type 的含义为:
- type=0,数据无特殊限制。
- type=1,保证 ∃1≤l′≤r′≤∣a∣,a[li,ri]+a[li,ri]=a[l′,r′]。
- type=2,保证 ∀r′−l′=ri−li+1,若 a[l′,r′−1]=a[li,ri],则必有 ar′=ali。
- type=3,保证 ∑ri−li≤105。
其中两个字符串 a+b 的结果为 a 和 b 按顺序拼接的字符串。
| 子任务编号 |
子任务分值 |
n≤ |
q≤ |
type= |
| 1 |
4 |
102 |
0 |
| 2 |
500 |
2000 |
| 3 |
2000 |
| 4 |
2×104 |
| 5 |
12 |
105 |
3 |
| 6 |
16 |
0 |
| 7 |
5×105 |
1 |
| 8 |
2 |
| 9 |
24 |
0 |