#P11725. [JOIG 2025] 修学旅行 / School Trip

[JOIG 2025] 修学旅行 / School Trip

题目描述

JOIG 高中有 3N3^N 名学生,编号从 113N3^N

JOIG 高中决定举行一场学校旅行,有两个可能的旅行目的地:阿拉斯加(记为“方案 A\texttt{A}”)和玻利维亚(记为“方案 B\texttt{B}”)。学生们决定使用以下的流程确定最终的旅行方案:

  • 考虑一个长度为 3N3^N 的字符串 SS:如果学生 i(1i3N)i\left(1\le i\le 3^N\right) 选择方案 A\texttt{A},那么 SiS_iA\texttt{A},否则为 B\texttt{B}
  • 执行以下操作 NN 次:
    • 假设当前 SS 的长度为 XX,考虑一个长度为 X3\frac{X}{3} 的字符串 SS',满足 Sj(1jX3)S'_j\left(1\le j\le\frac{X}{3}\right)S3j2,S3j1,S3jS_{3j-2},S_{3j-1},S_{3j} 中出现次数较多的字符(A\texttt{A}B\texttt{B});接着将 SS 替换为 SS'
  • 所有操作结束之后,SS 将成为一个长度为 11 的字符串(要么为 A\texttt{A} 要么为 B\texttt{B});如果 SSA\texttt{A},那么学校最终选取方案 A\texttt{A},否则选取方案 B\texttt{B}

初始时,我们使用一个字符串 TT 表示每名学生选择哪个方案:如果学生 i(1i3N)i\left(1\le i\le 3^N\right) 选择方案 A\texttt{A},那么 TiT_iA\texttt{A},否则为 B\texttt{B}

之后依次发生了 QQ 次事件,第 k(1kQ)k(1\le k\le Q) 次事件中,学生 pk(1pk3N)p_k\left(1\le p_k\le 3^N\right) 改变了其选择的方案,即若原来他 / 她选择方案 A\texttt{A},那么现在他 / 她选择的方案变为 B\texttt{B},反之亦然。

对于 k=1,2,,Qk=1,2,\ldots,Q,求出第 kk 次事件发生后,按照上述流程,学校会选择哪个旅行方案。

输入格式

第一行输入两个整数 N,QN,Q

第二行输入一个字符串 TT

接下来 QQ 行,每行一个整数 pkp_k

输出格式

输出 QQ 行,第 k(1kQ)k(1\le k\le Q) 行一个字符串表示第 kk 次事件过后学校选择的旅行方案:如果为 A\texttt{A},那么学校选择方案 A\texttt{A};如果为 B\texttt{B},那么学校选择方案 B\texttt{B}

2 3
ABABBAABB
3
8
4
B
B
A
2 5
AAAAAAAAA
1
2
7
8
5
A
A
A
B
B
1 4
AAB
3
1
2
3
A
A
B
B
3 6
AABABABBABAABABBBBBBAABABAA
4
1
9
3
8
9
B
B
B
B
B
A

提示

【样例解释 #1】

  • 在第 11 次事件发生后,确定方案流程中,SS 的变化为 ABBBBAABBBBBB\texttt{ABBBBAABB}\to\texttt{BBB}\to\texttt{B},最终选取方案 B\texttt{B}
  • 在第 22 次事件发生后,确定方案流程中,SS 的变化为 ABBBBAAABBBAB\texttt{ABBBBAAAB}\to\texttt{BBA}\to\texttt{B},最终选取方案 B\texttt{B}
  • 在第 33 次事件发生后,确定方案流程中,SS 的变化为 ABBABAAABBAAA\texttt{ABBABAAAB}\to\texttt{BAA}\to\texttt{A},最终选取方案 A\texttt{A}

该样例满足子任务 2,52,5 的限制。

【样例解释 #2】

该样例满足子任务 2,4,52,4,5 的限制。

【样例解释 #3】

该样例满足子任务 1,2,3,51,2,3,5 的限制。

【样例解释 #4】

该样例满足子任务 2,52,5 的限制。

【数据范围】

  • 1N121\le N\le 12
  • 1Q2×1051\le Q\le 2\times 10^5
  • TT 是长度为 NN 且仅包含大写字母 A\texttt{A}B\texttt{B} 的字符串;
  • 1pk3N(1kQ)1\le p_k\le 3^N(1\le k\le Q)

【子任务】

  1. 88 分)N=1N=1
  2. 1717 分)Q10Q\le 10
  3. 2222 分)pk5(1kQ)p_k\le 5(1\le k\le Q)
  4. 2828 分)TT 中所有字符均为 A\texttt{A} 且之后的修改均满足 pkpl(1k<lQ)p_k\ne p_l(1\le k<l\le Q)
  5. 2525 分)无附加限制。