企业官网建设流程全解析

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

题目描述

JOIG 高中有3N3^N3N名学生，编号从111到3N3^N3N。

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

• 考虑一个长度为3N3^N3N的字符串SSS：如果学生i(1≤i≤3N)i\left(1\le i\le 3^N\right)i(1≤i≤3N)选择方案A\texttt{A}A，那么SiS_iSi​为A\texttt{A}A，否则为B\texttt{B}B；
• 执行以下操作NNN次：
  • 假设当前SSS的长度为XXX，考虑一个长度为X3\frac{X}{3}3X​的字符串S′S'S′，满足Sj′(1≤j≤X3)S'_j\left(1\le j\le\frac{X}{3}\right)Sj′​(1≤j≤3X​)为S3j−2,S3j−1,S3jS_{3j-2},S_{3j-1},S_{3j}S3j−2​,S3j−1​,S3j​中出现次数较多的字符（A\texttt{A}A或B\texttt{B}B）；接着将SSS替换为S′S'S′；
• 所有操作结束之后，SSS将成为一个长度为111的字符串（要么为A\texttt{A}A要么为B\texttt{B}B）；如果SSS为A\texttt{A}A，那么学校最终选取方案A\texttt{A}A，否则选取方案B\texttt{B}B。

初始时，我们使用一个字符串TTT表示每名学生选择哪个方案：如果学生i(1≤i≤3N)i\left(1\le i\le 3^N\right)i(1≤i≤3N)选择方案A\texttt{A}A，那么TiT_iTi​为A\texttt{A}A，否则为B\texttt{B}B。

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

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

输入格式

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

第二行输入一个字符串TTT。

接下来QQQ行，每行一个整数pkp_kpk​。

输出格式

输出QQQ行，第k(1≤k≤Q)k(1\le k\le Q)k(1≤k≤Q)行一个字符串表示第kkk次事件过后学校选择的旅行方案：如果为A\texttt{A}A，那么学校选择方案A\texttt{A}A；如果为B\texttt{B}B，那么学校选择方案B\texttt{B}B。

输入输出样例 #1

输入 #1

2 3 ABABBAABB 3 8 4

输出 #1

B B A

输入输出样例 #2

输入 #2

2 5 AAAAAAAAA 1 2 7 8 5

输出 #2

A A A B B

输入输出样例 #3

输入 #3

1 4 AAB 3 1 2 3

输出 #3

A A B B

输入输出样例 #4

输入 #4

3 6 AABABABBABAABABBBBBBAABABAA 4 1 9 3 8 9

输出 #4

B B B B B A

说明/提示

【样例解释 #1】

• 在第111次事件发生后，确定方案流程中，SSS的变化为ABBBBAABB→BBB→B\texttt{ABBBBAABB}\to\texttt{BBB}\to\texttt{B}ABBBBAABB→BBB→B，最终选取方案B\texttt{B}B；
• 在第222次事件发生后，确定方案流程中，SSS的变化为ABBBBAAAB→BBA→B\texttt{ABBBBAAAB}\to\texttt{BBA}\to\texttt{B}ABBBBAAAB→BBA→B，最终选取方案B\texttt{B}B；
• 在第333次事件发生后，确定方案流程中，SSS的变化为ABBABAAAB→BAA→A\texttt{ABBABAAAB}\to\texttt{BAA}\to\texttt{A}ABBABAAAB→BAA→A，最终选取方案A\texttt{A}A。

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

【样例解释 #2】

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

【样例解释 #3】

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

【样例解释 #4】

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

【数据范围】

• 1≤N≤121\le N\le 121≤N≤12；
• 1≤Q≤2×1051\le Q\le 2\times 10^51≤Q≤2×105；
• TTT是长度为3N3^N3N且仅包含大写字母A\texttt{A}A和B\texttt{B}B的字符串；
• 1≤pk≤3N(1≤k≤Q)1\le p_k\le 3^N(1\le k\le Q)1≤pk​≤3N(1≤k≤Q)。

【子任务】

1. （888分）N=1N=1N=1；
2. （171717分）Q≤10Q\le 10Q≤10；
3. （222222分）pk≤5(1≤k≤Q)p_k\le 5(1\le k\le Q)pk​≤5(1≤k≤Q)；
4. （282828分）TTT中所有字符均为A\texttt{A}A且之后的修改均满足pk≠pl(1≤k<l≤Q)p_k\ne p_l(1\le k<l\le Q)pk​=pl​(1≤k<l≤Q)；
5. （252525分）无附加限制。

C++实现

#include<bits/stdc++.h>#defineintlonglong#defineIOSios::sync_with_stdio(false);cin.tie(0);cout.tie(0)usingnamespacestd;constintN=6e5+5;intPow(intx,inty){intres=1;while(y){if(y&1)res*=x;y>>=1;x*=x;}returnres;}intn,q;string t;boolans[N*4];//1表示B，0表示Aintls(intx){returnx*3-1;}//求左孩子intms(intx){returnx*3;}//求中间的孩子intrs(intx){returnx*3+1;}//求右孩子voidpush_up(intx){ans[x]=(ans[ls(x)]+ans[ms(x)]+ans[rs(x)]>=2);}voidbuild(intx,intl,intr){//建树if(l==r){ans[x]=t[l]-'A';return;}//赋值intmid=(r-l+1)/3;//区间长度build(ls(x),l,l+mid-1);//左区间build(ms(x),l+mid,l+mid*2-1);//中间区间build(rs(x),l+mid*2,r);//右区间push_up(x);//传递上去}voidupdate(intx,intk,intnowl,intnowr){//更新if(nowl==nowr){ans[x]=!ans[x];return;}//更新intmid=(nowr-nowl+1)/3;//同上if(k<=nowl+mid-1)update(ls(x),k,nowl,nowl+mid-1);elseif(nowl+mid*2<=k)update(rs(x),k,nowl+mid*2,nowr);elseupdate(ms(x),k,nowl+mid,nowl+mid*2-1);push_up(x);}signedmain(){IOS;cin>>n>>q;n=Pow(3,n);cin>>t;t=" "+t;build(1,1,n);for(inti=1,x;i<=q;i++){cin>>x;update(1,x,1,n);cout<<(ans[1]?'B':'A')<<endl;}return0;}