配点: 100 点
主席K. N 我们计划举办几天的会议。 1 会议将于当天举行 1 活动将在主会场A和分会场B或C举行。 使用 1 。
有关每次会议地点的信息,请访问
由 A, B, C, ? 组成的字符串
它由 S 给出。
i 日目 (1\leqq i \leqq N) 的会议地点是S 的 i 第一个字母是 A ,场地A,B ,场地B,
对于C ,场地 C,
在? 的情况下,它是不确定的。然而, 1 日和 N 由于第二天参加会议的人员较多,因此决定使用A会场。
从现在开始,对于尚未确定地点的会议,K 主席将选择地点 A、B 或 C。 1 您正在尝试分配一个。 另外,为了减轻交通负担,j 日和 j+1 会议地点可能因日期而异。 我们希望最小化 j (1\leqq j \leqq N-1)的数量。
关于尚未确定地点的会议分配, 我想考虑Q 场景并尝试最小化上述数字。 k 番目 (1 \leqq k \leqq Q)场景及其对应的问题如下。
- 关于地点尚未确定的会议,X_k 场地A,Y_k 场地B, 让我们将场地 C 分配给Z_k 。这时, 求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 \leqq k \leqq Q) 包含有关地点尚未确定的会议的信息。 如果您决定将场地 C 分配给 X_k 场地A, Y_k 场地B, 让我们将场地 C 分配给 Z_k 输出 j 日和 j+1 会议地点可能因日期而异。 我们希望最小化 j 的最小数量。 长度由
制約
- 2 \leqq N \leqq 300\,000.
- S 是
A,B,C,?组成 它是一个 N 字符串。 - S 的 1 信和 N 第一个字符是
包含在
A。 - 1 \leqq Q \leqq 200\,000.
- 0 \leqq X_k (1\leqq k \leqq Q).
- 0 \leqq Y_k (1\leqq k \leqq Q).
- 0 \leqq Z_k (1\leqq k \leqq Q).
- X_k + Y_k + Z_k 是 S 中
等于
?的数量 (1\leqq k \leqq Q). - N, Q, X_k, Y_k, Z_k是一个整数 (1\leqq k \leqq Q).
小課題
- (4 点) N \leqq 50,S 中
等于
?的数量是 13 以下. - (7 点) N \leqq 500.
- (13 点) N \leqq 5\,000,Q \leqq 10.
- (18 点) N \leqq 5\,000.
- (12 点) Q \leqq 10.
- (8 点) S 至
不包括
C, 在第Z_k = 0 (1\leqq k \leqq Q). - (13 点) Z_k = 0 (1\leqq k \leqq Q).
- (25 点)没有额外的限制。
入力例 1
9 A??B??C?A 3 1 3 1 4 1 0 0 0 5
出力例 1
3 4 4
1 个场景中,地点未定的会议 5 ,
将场地 C 分配给 1 场地A, 3 场地B,
让我们将场地 C 分配给 1 。
例如,每次会议的地点信息
一种可能的分配方法是 ABBBBCCAA 。在这种情况下, j 日和 j+1 会议地点可能因日期而异。
我们希望最小化 j 是 1,5,7 的 3 。
j 的数量
无法将数量减少到小于 2 ,因此
将场地 B 分配给 1 行是
一个整数,表示第 3 。
2 个场景中,地点未定的会议 5 ,
将场地 C 分配给 4 场地A, 1 。
例如,每次会议的地点信息
将场地 C 分配给所有 AAABBACAA 。在这种情况下,j 日和 j+1 会议地点可能因日期而异。
我们希望最小化 j 是 3,5,6,7 的 4 。
j 的数量
无法将数量减少到小于 3 ,因此
将场地 B 分配给 2 行是
一个整数,表示第 4 。
3 个场景中,地点未定的会议 5 。 j 日和 j+1 会议地点可能因日期而异。 我们希望最小化 j 是 1,3,4,8 的 4 件, 3 行是 一个整数,表示第 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
出力例 2
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
出力例 3
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 满足约束。