分数: 466 分
问题陈述
N 石头排列成圆圈。石头的编号是从 1 to N 按顺时针顺序,和石头 i 有小写英文字母 上面刻有 S_i 。从石头顺时针方向看下一块石头 N 是石头 1.
对于起始位置 x (1 \leq x \leq N)和长度 \ell (1 \leq \ell \leq N), 定义字符串 C(x, \ell) 如下:
- C(x, \ell): 长度的字符串 \ell 通过读取获得 \ell 从石头开始按顺时针顺序连续石头 x.
也就是说, k- 第一个字符 (1 \leq k \leq \ell) 的 C(x, \ell) 是刻在石头上的字符 ((x + k - 2) \bmod N) + 1.
高桥的当前位置由变量表示 P。初始值 P is 1.
Q 查询按顺序给出。在 i第一个查询,整数 给出 A_i 和 L_i ,执行以下操作:
移动:更新当前位置 P 到石头 A_i 沿顺时针方向位于前方。也就是说,
P \leftarrow ((P + A_i - 1) \bmod N) + 1
(当 A_i = 0, P 不变。)
计数:计算并输出以下值:
\#\{\, (x, \ell) \mid 1 \leq x \leq N,\ 1 \leq \ell \leq L_i,\ C(x, \ell) < C(P, \ell) \,\}
在这里, C(x, \ell) < C(P, \ell) 表示长度字符串之间的字典顺序比较 \ell,其中字典顺序遵循小写英文字母的通常顺序 \mathrm{a} < \mathrm{b} < \cdots < \mathrm{z}.
换句话说,在所有对中 (x, \ell) 与起始位置 x (1 \leq x \leq N)和长度 \ell (1 \leq \ell \leq L_i),计算其中的对数 C(x, \ell) 按字典顺序严格小于 C(P, \ell).
约束
- 1 \leq N \leq 3000
- 1 \leq Q \leq 10^5
- S 是一个长度为 N 由小写英文字母组成
- 0 \leq A_i \leq N - 1 (1 \leq i \leq Q)
- 1 \leq L_i \leq N (1 \leq i \leq Q)
- 所有输入均为整数(除了 S)
输入
N Q S A_1 L_1 A_2 L_2 \vdots A_Q L_Q
- 第一行包含石子数量 N 和查询数量 Q,用空格分隔。
- 第二行包含一个小写英文字符串 S 长度 N。的 i- 第一个字符 字符串的 S_i of S 代表刻在石头上的字符 i.
- 的 (2 + i)- 第行 (1 \leq i \leq Q) 包含移动量 A_i 和长度上限 L_i 为 i-第一个查询,以空格分隔。
输出
输出 Q 行。
关于 i第行,输出答案 i-第一个查询作为整数。
示例输入 1
5 4 abaca 0 1 1 3 3 5 4 2
示例输出 1
0 9 0 8
示例输入 2
4 5 aaaa 0 1 1 2 2 3 3 4 0 4
示例输出 2
0 0 0 0 0
示例输入 3
12 8 bananaabcxyz 0 6 5 4 11 12 3 7 8 2 1 10 10 11 6 5
示例输出 3
24 0 84 34 2 70 86 30
示例输入 4
30 15 qwertyuiopasdfghjklzxcvbnmabcd 0 1 29 30 15 10 7 25 3 3 28 30 14 1 1 29 20 15 5 30 0 12 11 20 27 7 6 18 2 30
示例输出 4
20 209 100 124 51 750 24 348 30 240 96 180 6 234 450
示例输入 5
1 5 z 0 1 0 1 0 1 0 1 0 1
示例输出 5
0 0 0 0 0