#P17703. [2026年江苏省队集训]串

    ID: 16687 传统题 9000ms 2048MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>CF2600字符串后缀数组树状数组二分算法基础数学

[2026年江苏省队集训]串

串

给定一个由小写字母组成的字符串 aa。

回答 qq 次询问,每次询问给定一个 aa 的子串 a[li,ri]a_{[l_i,r_i]},求有多少个字符串 ss 满足 ss 是 aa 的子串,且 s∞s^{\infin} 的字典序小于 a[li,ri]∞a_{[l_i,r_i]}^{\infin}。

对于一个字符串 tt,我们用 t∞t^{\infin} 表示 tt 不断重复得到的无穷字符串。

输入格式

输入的第一行包含一个只包含小写字母的字符串 aa 。

输入的第二行包含一个正整数 qq 和一个整数 typetype,其中 typetype 表示数据类型。

接下来 qq 行,第 ii 行包含两个整数 lil_i 和 rir_i。

输出格式

输出 qq 行,每行一个整数表示一个询问的答案。

样例输入与输出

abbab
5 0
1 3
2 4
3 5
1 4
2 5
4
7
6
2
8

样例解释

询问 11 对应的子串是 abb,满足条件的子串有 a,ab,abba,abbab 共 44 个。

数据范围与子任务

对于所有数据,满足 1≤li≤ri≤∣a∣≤5×1051\le l_i\le r_i\le |a| \le 5 \times 10^{5},1≤q≤5×1051\le q \le 5 \times 10^{5}。

下表中数据类型 typetype 的含义为:

  • type=0type=0,数据无特殊限制。
  • type=1type=1,保证 ∃1≤l′≤r′≤∣a∣\exists 1\le l'\le r'\le |a|,a[li,ri]+a[li,ri]=a[l′,r′]a_{[l_i,r_i]}+a_{[l_i,r_i]}=a_{[l',r']}。
  • type=2type=2,保证 ∀r′−l′=ri−li+1\forall r'-l'=r_i-l_i+1,若 a[l′,r′−1]=a[li,ri]a_{[l',r'-1]}=a_{[l_i,r_i]},则必有 ar′≠alia_{r'}\neq a_{l_i}。
  • type=3type=3,保证 ∑ri−li≤105\sum r_i-l_i \le 10^5。

其中两个字符串 a+ba+b 的结果为 aa 和 bb 按顺序拼接的字符串。

子任务编号 子任务分值 n≤n\le q≤q\le type=type=
11 44 10210^{2} 00
22 500500 20002000
33 20002000
44 2×1042 \times 10^{4}
55 1212 10510^{5} 33
66 1616 00
77 5×1055 \times 10^{5} 11
88 22
99 2424 00