← 返回题目列表

AtCoder · joisp2025_h

H. 会议

中文机器翻译题面 查看原题

配点: 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).

小課題

  1. (4 点) N \leqq 50,S 中 等于 ? 的数量是 13 以下.
  2. (7 点) N \leqq 500.
  3. (13 点) N \leqq 5\,000,Q \leqq 10.
  4. (18 点) N \leqq 5\,000.
  5. (12 点) Q \leqq 10.
  6. (8 点) S 至 不包括 C , 在第Z_k = 0 (1\leqq k \leqq Q).
  7. (13 点) Z_k = 0 (1\leqq k \leqq Q).
  8. (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 满足约束。