配点 : 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 是一个整数
小課題
- (10 点) T_i=1
- (50 点) T_i=2
- (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