P16375 [IATI 2026] Evilution

好人们计划通过电离辐射射击坏人来击败他们。为了校准武器，好人们需要了解坏人 DNA 中某个区间的组成。坏人们不仅仅是坏 —— 他们非常邪恶 —— 因此，他们每天都在进化：他们会将 DNA 中的每个字母 $\texttt{A}$、$\texttt{C}$、$\texttt{G}$ 和 $\texttt{T}$ 替换为对应的、长度**至少为 2** 的字符串：$S_\texttt{A}$、$S_\texttt{C}$、$S_\texttt{G}$ 和 $S_\texttt{T}$。战斗将会持续很多天，因此好人们需要回答 $Q$ 个不同的询问，每个询问包含三个数字 —— $K_i$、$L_i$ 和 $R_i$。对于每个询问，你需要报告四个数字，分别对应第 $K_i$ 天时坏人 DNA 的闭区间 $[L_i; R_i]$ 内字母 $\texttt{A}$、$\texttt{C}$、$\texttt{G}$ 和 $\texttt{T}$ 的数量。 ### 实现细节 你需要实现函数 $\texttt{solve}$： ```cpp std::vector solve( std::string S_0, std::vector S_ACGT, std::vector K, std::vector L, std::vector R ) ``` - $S_0$：第 $0$ 天时坏人的 DNA。 - $S_\texttt{ACGT}$：包含 $4$ 个字符串 $S_\texttt{A}, S_\texttt{C}, S_\texttt{G}, S_\texttt{T}$ 的向量。 - $K$：包含 $Q$ 个非负整数的向量，其中第 $i$ 个整数为 $K_i$。 - $L$：包含 $Q$ 个非负整数的向量，其中第 $i$ 个整数为 $L_i$。 - $R$：包含 $Q$ 个非负整数的向量，其中第 $i$ 个整数为 $R_i$。 对于每个测试用例，该函数会被恰好调用一次。它需要返回一个由 $Q$ 个包含 $4$ 个元素的向量组成的向量 —— 分别对应每个询问中 $\texttt{A}$、$\texttt{C}$、$\texttt{G}$ 和 $\texttt{T}$ 的数量。

输入格式： - 第 $1$ 行到第 $5$ 行：依次为 $S_0, S_\texttt{A}, S_\texttt{C}, S_\texttt{G}, S_\texttt{T}$。 - 第 $6$ 行：$Q$ —— 询问的数量。 - 第 $7$ 行到第 $7+(Q-1)$ 行：每行依次为 $K_i$, $L_i$, $R_i$。

输出格式： - 第 $i$ 行 —— 第 $i$ 次调用所返回的四个数字。

### 样例解释 坏人在第 $0$ 天、第 $1$ 天和第 $2$ 天的 DNA 如下： - $\tt TAG$ - $\tt CGCTGTCCT$ - $\tt CGTCCTCGTCGCCCTCGCCGTCGTCGC$ ### 数据范围 - $2 \le S \le 10^5$，其中 $S = \max(|S_0|, |S_\texttt{A}|, |S_\texttt{C}|, |S_\texttt{G}|, |S_\texttt{T}|)$ - 保证所有字符串中的字母均为 $\texttt{A}$、$\texttt{C}$、$\texttt{G}$ 或 $\texttt{T}$。 - $1 \le Q \le 10^4$ - 对于所有 $0 \le i \le Q-1$，满足 $0 \le K_i \le 10^{18}$ - 对于所有 $0 \le i \le Q-1$，满足 $0 \le L_i \le R_i \le 10^{18}$ - 保证对于所有询问，区间 $[L_i, R_i]$ 内的位置均存在对应的字母。 ### 子任务 | **子任务** | **分数** | **依赖子任务** | **$S$** | **$Q$** | **$K_i$** | **其他约束** | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | $0$ | $0$ | $-$ | $--$ | $--$ | $--$ | 样例测试。 | | $1$ | $7$ | $0$ | $\le 5$ | $\le 100$ | $\le 10$ | $--$ | | $2$ | $6$ | $0-1$ | $\le 6$ | $\le 10^4$ | $\le 10$ | $--$ | | $3$ | $13$ | $0-2$ | $\le 10^3$ | $\le 10^4$ | $\le 50$ | $--$ | | $4$ | $10$ | $0-3$ | $\le 10^5$ | $\le 10^4$ | $\le 50$ | $--$ | | $5$ | $15$ | $0-4$ | $\le 10^5$ | $\le 10^4$ | $\le 2 \times 10^3$ | $--$ | | $6$ | $7$ | $-$ | $\le 10^5$ | $\le 10^4$ | $\le 10^{18}$ | $L_i = R_i = 0$。 | | $7$ | $17$ | $0-3$ | $\le 10^3$ | $\le 10^4$ | $\le 10^{18}$ | $--$ | | $8$ | $25$ | $0-7$ | $\le 10^5$ | $\le 10^4$ | $\le 10^{18}$ | $--$ | 仅当某个子任务的所有测试点及其依赖子任务的所有测试点均成功通过时，才能获得该子任务的分数。 翻译由 DeepSeek V4 Pro 完成