P11725 [JOIG 2025] 修學(xué)旅行 / School Trip題目描述JOIG 高中有3N3^N3N名學(xué)生編號(hào)從111到3N3^N3N。JOIG 高中決定舉行一場(chǎng)學(xué)校旅行有兩個(gè)可能的旅行目的地阿拉斯加記為“方案A\texttt{A}A”和玻利維亞記為“方案B\texttt{B}B”。學(xué)生們決定使用以下的流程確定最終的旅行方案考慮一個(gè)長(zhǎng)度為3N3^N3N的字符串SSS如果學(xué)生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執(zhí)行以下操作NNN次假設(shè)當(dāng)前SSS的長(zhǎng)度為XXX考慮一個(gè)長(zhǎng)度為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?中出現(xiàn)次數(shù)較多的字符A\texttt{A}A或B\texttt{B}B接著將SSS替換為S′SS′所有操作結(jié)束之后SSS將成為一個(gè)長(zhǎng)度為111的字符串要么為A\texttt{A}A要么為B\texttt{B}B如果SSS為A\texttt{A}A那么學(xué)校最終選取方案A\texttt{A}A否則選取方案B\texttt{B}B。初始時(shí)我們使用一個(gè)字符串TTT表示每名學(xué)生選擇哪個(gè)方案如果學(xué)生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。之后依次發(fā)生了QQQ次事件第k(1≤k≤Q)k(1\le k\le Q)k(1≤k≤Q)次事件中學(xué)生pk(1≤pk≤3N)p_k\left(1\le p_k\le 3^N\right)pk?(1≤pk?≤3N)改變了其選擇的方案即若原來(lái)他 / 她選擇方案A\texttt{A}A那么現(xiàn)在他 / 她選擇的方案變?yōu)锽\texttt{B}B反之亦然。對(duì)于k1,2,…,Qk1,2,\ldots,Qk1,2,…,Q求出第kkk次事件發(fā)生后按照上述流程學(xué)校會(huì)選擇哪個(gè)旅行方案。輸入格式第一行輸入兩個(gè)整數(shù)N,QN,QN,Q。第二行輸入一個(gè)字符串TTT。接下來(lái)QQQ行每行一個(gè)整數(shù)pkp_kpk?。輸出格式輸出QQQ行第k(1≤k≤Q)k(1\le k\le Q)k(1≤k≤Q)行一個(gè)字符串表示第kkk次事件過(guò)后學(xué)校選擇的旅行方案如果為A\texttt{A}A那么學(xué)校選擇方案A\texttt{A}A如果為B\texttt{B}B那么學(xué)校選擇方案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說(shuō)明/提示【樣例解釋 #1】在第111次事件發(fā)生后確定方案流程中SSS的變化為ABBBBAABB→BBB→B\texttt{ABBBBAABB}\to\texttt{BBB}\to\texttt{B}ABBBBAABB→BBB→B最終選取方案B\texttt{B}B在第222次事件發(fā)生后確定方案流程中SSS的變化為ABBBBAAAB→BBA→B\texttt{ABBBBAAAB}\to\texttt{BBA}\to\texttt{B}ABBBBAAAB→BBA→B最終選取方案B\texttt{B}B在第333次事件發(fā)生后確定方案流程中SSS的變化為ABBABAAAB→BAA→A\texttt{ABBABAAAB}\to\texttt{BAA}\to\texttt{A}ABBABAAAB→BAA→A最終選取方案A\texttt{A}A。該樣例滿足子任務(wù)2,52,52,5的限制?！緲永忉?#2】該樣例滿足子任務(wù)2,4,52,4,52,4,5的限制?！緲永忉?#3】該樣例滿足子任務(wù)1,2,3,51,2,3,51,2,3,5的限制?！緲永忉?#4】該樣例滿足子任務(wù)2,52,52,5的限制?！緮?shù)據(jù)范圍】1≤N≤121\le N\le 121≤N≤121≤Q≤2×1051\le Q\le 2\times 10^51≤Q≤2×105TTT是長(zhǎng)度為3N3^N3N且僅包含大寫(xiě)字母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)?！咀尤蝿?wù)】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)pk?pl?(1≤kl≤Q)252525分無(wú)附加限制。C實(shí)現(xiàn)#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){//建樹(shù)if(lr){ans[x]t[l]-A;return;}//賦值intmid(r-l1)/3;//區(qū)間長(zhǎng)度build(ls(x),l,lmid-1);//左區(qū)間build(ms(x),lmid,lmid*2-1);//中間區(qū)間build(rs(x),lmid*2,r);//右區(qū)間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;}