![打卡信奥刷题（3610）用C++实现信奥题 P11725 [JOIG 2025] 修学旅行 / School Trip](http://pic.xiahunao.cn/yaotu/打卡信奥刷题（3610）用C++实现信奥题 P11725 [JOIG 2025] 修学旅行 / School Trip)
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′SS′满足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′SS′所有操作结束之后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反之亦然。对于k1,2,…,Qk1,2,\ldots,Qk1,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输入 #12 3 ABABBAABB 3 8 4输出 #1B B A输入输出样例 #2输入 #22 5 AAAAAAAAA 1 2 7 8 5输出 #2A A A B B输入输出样例 #3输入 #31 4 AAB 3 1 2 3输出 #3A A B B输入输出样例 #4输入 #43 6 AABABABBABAABABBBBBBAABABAA 4 1 9 3 8 9输出 #4B 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≤121≤Q≤2×1051\le Q\le 2\times 10^51≤Q≤2×105TTT是长度为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)。【子任务】888分N1N1N1171717分Q≤10Q\le 10Q≤10222222分pk≤5(1≤k≤Q)p_k\le 5(1\le k\le Q)pk≤5(1≤k≤Q)282828分TTT中所有字符均为A\texttt{A}A且之后的修改均满足pk≠pl(1≤kl≤Q)p_k\ne p_l(1\le kl\le Q)pkpl(1≤kl≤Q)252525分无附加限制。C实现#includebits/stdc.h#defineintlonglong#defineIOSios::sync_with_stdio(false);cin.tie(0);cout.tie(0)usingnamespacestd;constintN6e55;intPow(intx,inty){intres1;while(y){if(y1)res*x;y1;x*x;}returnres;}intn,q;string t;boolans[N*4];//1表示B0表示Aintls(intx){returnx*3-1;}//求左孩子intms(intx){returnx*3;}//求中间的孩子intrs(intx){returnx*31;}//求右孩子voidpush_up(intx){ans[x](ans[ls(x)]ans[ms(x)]ans[rs(x)]2);}voidbuild(intx,intl,intr){//建树if(lr){ans[x]t[l]-A;return;}//赋值intmid(r-l1)/3;//区间长度build(ls(x),l,lmid-1);//左区间build(ms(x),lmid,lmid*2-1);//中间区间build(rs(x),lmid*2,r);//右区间push_up(x);//传递上去}voidupdate(intx,intk,intnowl,intnowr){//更新if(nowlnowr){ans[x]!ans[x];return;}//更新intmid(nowr-nowl1)/3;//同上if(knowlmid-1)update(ls(x),k,nowl,nowlmid-1);elseif(nowlmid*2k)update(rs(x),k,nowlmid*2,nowr);elseupdate(ms(x),k,nowlmid,nowlmid*2-1);push_up(x);}signedmain(){IOS;cinnq;nPow(3,n);cint;t t;build(1,1,n);for(inti1,x;iq;i){cinx;update(1,x,1,n);cout(ans[1]?B:A)endl;}return0;}
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′SS′满足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′SS′所有操作结束之后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反之亦然。对于k1,2,…,Qk1,2,\ldots,Qk1,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输入 #12 3 ABABBAABB 3 8 4输出 #1B B A输入输出样例 #2输入 #22 5 AAAAAAAAA 1 2 7 8 5输出 #2A A A B B输入输出样例 #3输入 #31 4 AAB 3 1 2 3输出 #3A A B B输入输出样例 #4输入 #43 6 AABABABBABAABABBBBBBAABABAA 4 1 9 3 8 9输出 #4B 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≤121≤Q≤2×1051\le Q\le 2\times 10^51≤Q≤2×105TTT是长度为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)。【子任务】888分N1N1N1171717分Q≤10Q\le 10Q≤10222222分pk≤5(1≤k≤Q)p_k\le 5(1\le k\le Q)pk≤5(1≤k≤Q)282828分TTT中所有字符均为A\texttt{A}A且之后的修改均满足pk≠pl(1≤kl≤Q)p_k\ne p_l(1\le kl\le Q)pkpl(1≤kl≤Q)252525分无附加限制。C实现#includebits/stdc.h#defineintlonglong#defineIOSios::sync_with_stdio(false);cin.tie(0);cout.tie(0)usingnamespacestd;constintN6e55;intPow(intx,inty){intres1;while(y){if(y1)res*x;y1;x*x;}returnres;}intn,q;string t;boolans[N*4];//1表示B0表示Aintls(intx){returnx*3-1;}//求左孩子intms(intx){returnx*3;}//求中间的孩子intrs(intx){returnx*31;}//求右孩子voidpush_up(intx){ans[x](ans[ls(x)]ans[ms(x)]ans[rs(x)]2);}voidbuild(intx,intl,intr){//建树if(lr){ans[x]t[l]-A;return;}//赋值intmid(r-l1)/3;//区间长度build(ls(x),l,lmid-1);//左区间build(ms(x),lmid,lmid*2-1);//中间区间build(rs(x),lmid*2,r);//右区间push_up(x);//传递上去}voidupdate(intx,intk,intnowl,intnowr){//更新if(nowlnowr){ans[x]!ans[x];return;}//更新intmid(nowr-nowl1)/3;//同上if(knowlmid-1)update(ls(x),k,nowl,nowlmid-1);elseif(nowlmid*2k)update(rs(x),k,nowlmid*2,nowr);elseupdate(ms(x),k,nowlmid,nowlmid*2-1);push_up(x);}signedmain(){IOS;cinnq;nPow(3,n);cint;t t;build(1,1,n);for(inti1,x;iq;i){cinx;update(1,x,1,n);cout(ans[1]?B:A)endl;}return0;}
