← 返回题目列表

AtCoder · awc0090_e

E. 圆弦的字典顺序

中文机器翻译题面 查看原题

分数: 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 ,执行以下操作:

  1. 移动:更新当前位置 P 到石头 A_i 沿顺时针方向位于前方。也就是说,

    P \leftarrow ((P + A_i - 1) \bmod N) + 1

    (当 A_i = 0, P 不变。)

  2. 计数:计算并输出以下值:

    \#\{\, (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