#5051. 「JOISC 2025 Day3」会议

题目译自 JOISC 2025 Day3 T2 「会議 / Conference」

题目描述

K 理事长计划组织一场为期 $N$ 天的会议，每天举办一场。会议地点可选为主会场 A 或副会场 B、C 中的一个。

每场会议的场地信息由一个长度为 $N$ 的字符串 $S$ 表示，包含字符 A、B、C 或 ?。第 $i$ ($1 \leq i \leq N$) 天的会议若 $S$ 的第 $i$ 个字符为 A，则在会场 A 举行；B 则为会场 B，C 为会场 C，? 表示待定。不过，第 $1$ 天和第 $N$ 天因参会人数众多，已确定使用会场 A。

现在，K 理事长需要为所有待定会议指定会场 A、B 或 C 中的一个。为了减少移动负担，他希望尽量减少相邻两天（第 $j$ 天和第 $j+1$ 天，$1 \leq j \leq N-1$）场地不同的情况数。

你需要针对 $Q$ 个安排方案，计算这种最小情况数。第 $k$ ($1 \leq k \leq Q$) 个方案及其问题是：

将待定会议分配为 $X_k$ 个 A、$Y_k$ 个 B 和 $Z_k$ 个 C，求相邻两天场地不同的 $j$ 的最小个数。

给定场地信息和方案详情，编写程序回答这些问题。

输入格式

第一行包含一个整数 $N$。

第二行包含一个字符串 $S$。

第三行包含一个整数 $Q$。

接下来的 $Q$ 行，每行包含三个整数 $X_i, Y_i, Z_i$。

输出格式

输出 $Q$ 行。第 $k$ ($1 \leq k \leq Q$) 行输出将待定会议分配为 $X_k$ 个 A、$Y_k$ 个 B、$Z_k$ 个 C 时，相邻两天场地不同的 $j$ 的最小个数。

样例 1

输入

9
A??B??C?A
3
1 3 1
4 1 0
0 0 5

输出

3
4
4

解释
在第 $1$ 个方案中，对于 $5$ 个尚未确定场地的会议，分配 $1$ 个到会场 A，$3$ 个到会场 B，$1$ 个到会场 C。例如，可以分配为 ABBBBCCAA，此时连续两天会议场地不同的情况有第 $1$、$5$、$7$ 天，共 $3$ 个。无法使这种情况少于 $2$ 个，因此第一行输出 $3$。

在第 $2$ 个方案中，对于 $5$ 个尚未确定场地的会议，分配 $4$ 个到会场 A，$1$ 个到会场 B。例如，可以分配为 AAABBACAA，此时连续两天会议场地不同的情况有第 $3$、$5$、$6$、$7$ 天，共 $4$ 个。无法使这种情况少于 $3$ 个，因此第二行输出 $4$。

在第 $3$ 个方案中，对于 $5$ 个尚未确定场地的会议，全部分配到会场 C。此时连续两天会议场地不同的情况有第 $1$、$3$、$4$、$8$ 天，共 $4$ 个，因此第三行输出 $4$。

这个样例满足子任务 $1,2,3,4,5,8$ 的限制。

样例 2

输入

12
A???A?B????A
4
0 8 0
2 6 0
7 1 0
3 5 0

输出

4
4
2
2

此样例满足所有子任务的限制。

样例 3

输入

28
ACB??B???BCB??B????B?AAA?BBA
26
6 1 6
4 5 4
2 3 8
9 2 2
11 0 2
8 4 1
11 0 2
2 0 11
0 1 12
12 1 0
10 3 0
1 4 8
3 7 3
2 8 3
1 3 9
11 1 1
7 0 6
6 4 3
8 4 1
0 10 3
13 0 0
11 1 1
0 6 7
2 8 3
9 0 4
0 0 13

输出

15
11
13
13
15
12
15
15
16
15
13
12
10
9
13
15
15
11
12
9
15
15
11
9
15
17

这个样例满足子任务 $1,2,4,8$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 300000$
• $S$ 是长度为 $N$ 的字符串，包含 A、B、C 或 ?
• $S$ 的第 $1$ 和第 $N$ 个字符为 A
• $1 \leq Q \leq 200000$
• $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$ ($1 \leq k \leq Q$) 等于 $S$ 中 ? 的个数
• $N, Q, X_k, Y_k, Z_k$ ($1 \leq k \leq Q$) 为整数

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
1	4	$N \leq 50$，$S$ 中 ? 个数 $\leq 13$
2	7	$N \leq 500$
3	13	$N \leq 5000$, $Q \leq 10$
4	18	$N \leq 5000$
5	12	$Q \leq 10$
6	8	$S$ 无 C，$Z_k = 0$ ($1 \leq k \leq Q$)
7	13	$Z_k = 0$ ($1 \leq k \leq Q$)
8	25	无附加限制