P11990 [JOIST 2025] 大会 / Conference

K 主席计划在接下来 $N$ 天内举办一系列会议，每天都会举办恰好一场会议，且会议将在三个场馆之一举行：主场馆 A 或两个副场馆 B 和 C 中的一个。 每场会议的场馆信息由字符串 $S$ 给出，该字符串由 $\texttt{A}$、$\texttt{B}$、$\texttt{C}$ 和 $\texttt{?}$ 组成。对于第 $i$ 天（$1 \leq i \leq N$），如果 $S$ 的第 $i$ 个字符是 $\texttt{A}$，则会议在场馆 A 举行；如果是 $\texttt{B}$，则在场馆 B 举行；如果是 $\texttt{C}$，则在场馆 C 举行；如果是 $\texttt{?}$，则表示第 $i$ 天的场馆尚未决定。 由于第一天和第 $N$ 天的会议预计会有大量参与者，因此已确定**这两天必须使用场馆 A**。 现在，K 主席需要为每个未决定的会议分配场馆（每个 $\texttt{?}$ 处可以选择 A、B 或 C）。此外，为了最小化场馆间移动的负担，他希望最小化满足以下条件的索引 $j$（$1 \leq j \leq N-1$）的数量：第 $j$ 天的场馆与第 $(j+1)$ 天的场馆不同。 现在需要考虑 $Q$ 个分配场景。对于第 $k$ 个场景（$1 \leq k \leq Q$）及其对应的问题描述如下： - K 主席必须将 $X_k$ 个未决定的会议分配到场馆 A，$Y_k$ 个分配到场馆 B，$Z_k$ 个分配到场馆 C。 - 请确定在此条件下，满足「第 $j$ 天的场馆与第 $(j+1)$ 天的场馆不同」的最小可能索引 $j$ 的数量。 给定场馆信息和需要考量的场景，请编写程序回答这些问题。

> $N$\ > $S$\ > $Q$\ > $X_1$ $Y_1$ $Z_1$\ > $X_2$ $Y_2$ $Z_2$\ > $\vdots$\ > $X_Q$ $Y_Q$ $Z_Q$

输出 $Q$ 行。 在第 $k$ 行（$1 \leq k \leq Q$）中，输出在 K 主席将 $X_k$ 个未决定会议分配到 A，$Y_k$ 个分配到 B，$Z_k$ 个分配到 C 的条件下，满足「第 $j$ 天的场馆与第 $(j+1)$ 天的场馆不同」的最小可能索引 $j$ 的数量。

### 样例解释 #### 样例解释 $1$ 在第一个场景中，K 主席需要将 $5$ 个未决定会议中的 $1$ 个分配到场馆 A，$3$ 个分配到 B，$1$ 个分配到 C。例如，一种可能的分配结果会生成场馆信息字符串 $\texttt{ABBBBCCAA}$。此时，满足"第 $j$ 天的场馆与第 $(j+1)$ 天的场馆不同"的索引 $j$ 是 $1$、$5$、$7$，共 $3$ 个。由于无法将这个数量减少到 $2$ 或更少，因此第一行的正确输出是 $3$。 在第二个场景中，K 主席需要将 $5$ 个未决定会议中的 $4$ 个分配到 A，$1$ 个分配到 B。例如，一种可能的分配结果会生成字符串 $\texttt{AAABBACAA}$。此时，满足条件的索引 $j$ 是 $3$、$5$、$6$、$7$，共 $4$ 个。因此第二行的正确输出是 $4$。 在第三个场景中，K 主席需要将所有 $5$ 个未决定会议分配到 C。满足条件的索引 $j$ 是 $1$、$3$、$4$、$8$，共 $4$ 个。因此第三行的正确输出是 $4$。 该样例满足子任务 $1\sim 5,8$ 的限制。 #### 样例解释 $2$ 该样例满足所有子任务的限制。 #### 样例解释 $3$ 该样例满足子任务 $1,2,4,8$ 的限制。 ### 数据范围 - $2 \leq N \leq 300\,000$； - $S$ 是长度为 $N$ 且由 $\texttt{A}$、$\texttt{B}$、$\texttt{C}$ 和 $\texttt{?}$ 组成的字符串； - $S$ 的首字符和末字符均为 $\texttt{A}$； - $1 \leq Q \leq 200\,000$； - $0 \leq X_k$（$1 \leq k \leq Q$）； - $0 \leq Y_k$（$1 \leq k \leq Q$）； - $0 \leq Z_k$（$1 \leq k \leq Q$）； - $X_k + Y_k + Z_k$ 等于 $S$ 中 $\texttt{?}$ 的数量（$1 \leq k \leq Q$）； - $N$、$Q$、$X_k$、$Y_k$、$Z_k$ 均为整数。 ### 子任务 - $\text{Subtask 1 (4 pts)}$：$N \leq 50$ 且 $S$ 中 $\texttt{?}$ 的数量不超过 $13$； - $\text{Subtask 2 (7 pts)}$：$N \leq 500$； - $\text{Subtask 3 (13 pts)}$：$N \leq 5\,000$，$Q \leq 10$； - $\text{Subtask 4 (18 pts)}$：$N \leq 5\,000$； - $\text{Subtask 5 (12 pts)}$：$Q \leq 10$； - $\text{Subtask 6 (8 pts)}$：$S$ 不含 $\texttt{C}$ 且所有 $Z_k = 0$（$1 \leq k \leq Q$）； - $\text{Subtask 7 (13 pts)}$：所有 $Z_k = 0$（$1 \leq k \leq Q$）； - $\text{Subtask 8 (25 pts)}$：无额外限制。