← 返回题目列表

AtCoder · pakencamp_2025_day3_o

O. 长颈鹿?斑马?

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

配点 : 100 点

致环球杯参赛者

当包含在 Universal Cup 中时,此问题将被删除。因此,当使用 AtCoder 结果进行 Universal Cup 时,我们建议先解决其他问题。 给出了


問題文

整数 G 和 还给出了0 和 按字典顺序比较 1 由……组成的字符串 S 。 对于

是 小于或等于0 和 按字典顺序比较 1 组成的非空字符串是

  • 长颈鹿绳表示长度为 G 或更多。
  • 斑马线表示没有相同字符的相邻部分(长度 字符串 1 是斑马线)。
  • 霍加狓字符串表示它既不是长颈鹿绳也不是斑马绳。 给定

Q 请处理一个查询。i 个查询中,整数 L_i,R_i,T_i ,请回答以下查询。

  • S 可以得到第 L_i 从第一个字符开始 R_i 在提取字符的字符串中包含的子字符串中, 当
    • T_i=1 时,回答长颈鹿绳的数量。 当
    • T_i=2 时,回答斑马线的数量。 当
    • T_i=3 时,回答霍加皮字符串的数量。

但是,即使从不同位置检索相同的字符串,它也会被视为不同的子字符串。

制約

  • 1\leq G\leq |S|
  • 1\leq |S| \leq 2\times 10^5
  • S 是 您也可以写 0 和 按字典顺序比较 1 组成
  • 1\leq Q\leq 2\times 10^5
  • 1\leq L_i\leq R_i\leq N
  • 1\leq T_i\leq 3
  • G,Q,L_i,R_i,T_i 是一个整数

小課題

  1. (10 点) T_i=1
  2. (50 点) T_i=2
  3. (40 点)没有额外的限制。

入力

输入是按以下格式从标准输入给出的。

G
S
Q
L_1 R_1 T_1
L_2 R_2 T_2
\vdots
L_Q R_Q T_Q

出力

Q 行。

i 行中,i 个查询的答案。


入力例 1

3
010010
3
1 6 1
1 6 2
1 6 3

出力例 1

10
12
1