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

看没有题解，交一发。

题目传送门

思路

看到题面容易想到用线段树做，但是这道题要用一个形状为满三叉树的线段树，这样才方便统计答案。

首先来看节点的编号，从上到下，从左到右依次给树上的节点进行编号，容易发现，设一个非叶子节点的编号为 $x$，则它的三个儿子节点的编号为 $3x-1,3x,3x+1$，配一张图方便大家理解（图微丑，轻喷）。

所以在建树和修改时，就可以直接算出子节点的编号。

剩下的就和线段树差不多了，直接上代码。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+6;//数组开大一点
int n,q;
bool t[N];
char s[N];
void build(int cur,int l,int r){//建树if(l==r){t[cur]=s[l]-'A';//0表示A,1表示Breturn;}int mid1=l+(r-l+1)/3-1,mid2=l+2*(r-l+1)/3-1;//将区间平均分成三部分build(cur*3-1,l,mid1);build(cur*3,mid1+1,mid2);build(cur*3+1,mid2+1,r);t[cur]=(t[cur*3-1]+t[cur*3]+t[cur*3+1]>1);//如果1的个数大于1，则B多，否则A多
}
void modify(int cur,int l,int r,int x){//单点修改if(l==r && l==x){t[cur]^=1;//修改return;}int mid1=l+(r-l+1)/3-1,mid2=l+2*(r-l+1)/3-1;if(x<=mid1)modify(cur*3-1,l,mid1,x);else if(x<=mid2)modify(cur*3,mid1+1,mid2,x);elsemodify(cur*3+1,mid2+1,r,x);t[cur]=(t[cur*3-1]+t[cur*3]+t[cur*3+1]>1);//重新统计答案
}
int main(){scanf("%d%d",&n,&q);scanf("%s",s+1);n=strlen(s+1);build(1,1,n);while(q--){int p;scanf("%d",&p);modify(1,1,n,p);printf("%c\n",t[1]+'A');//t[1]为最终的结果输出}return 0;
}