AT_pakencamp_2025_day3_o Giraffe? Zebra?

给定一个整数 $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$ 时，输出其中“霍加皮字符串”的数量。 注意：即使字符串内容相同，若起止位置不同，也视为不同的子串。

输入按以下格式从标准输入读入： > $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$ 个查询的答案。

### Universal Cup 参赛者注意 由于本题会在 Universal Cup 收录时被删除，如在 Universal Cup 中使用 AtCoder 的结果，建议优先完成本题之外的题目。 ### 子任务 1. ($10$ 分) $T_i=1$ 2. ($50$ 分) $T_i=2$ 3. ($40$ 分) 没有额外限制。 ### 约束条件 - $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$ 均为整数 由 ChatGPT 5 翻译