一道名副其实的 hot tea
首先显然可以发现这俩人在玩 Nim 游戏，因此对于一个 \(c_i\in[l,r]\) 其 SG 值就是 \(c_i-l\)，最终游戏的 SG 值就是 \(\oplus_{c_i\in[l,r]}(c_i-l)\)，如果该值为 \(0\) 答案就是 B，否则答案是 A。
从这一步开始就有好几种不同复杂度的做法了，下面将一一介绍它们。
下视 \(n,m,q\) 同阶。
做法一：暴力
迫真 · \(2\times 10^5\) 给 \(n^2\) 暴力踩过去。
你看这 \(2\times 10^5\) 的数据范围，你不写 \(n^2\) 写啥呢，难道还傻傻地想 \(n\log^2n\) 或是 \(n\log n\) 的做法？
不要笑，现场 rk1 那位大哥就是暴力碾标算还抵过了 100 多发 hack。不得不说 CF 机子是真的快（
就没啥好说的了，暴力从第一个 \(\ge l\) 的位置开始枚举把它们异或起来即可。
时间复杂度 \(n^2\)。
做法二：莫队+01-trie
允许离线+静态区间问题，这无不启发我们往莫队的方向想。又因为此题涉及异或，因此考虑 01-trie，具体来说我们建立一棵 01-trie 维护当前莫队表示的区间中所有元素与 \(l\)，那么向左/右移动右端点时 01-trie 时删除/插入元素，这个维护起来异常容易的不再赘述。向左/右移动左端点时需要先将 01-trie 中所有元素 \(+1/-1\) 再插入/删除新的元素，全局 \(\pm 1\) 这个操作的维护方法算是经典套路了，考虑从低到高将序列中的元素插入 01-trie，那么全局 \(+1\) 相当于从根节点开始 DFS，每次 DFS 时交换当前节点两个儿子再 DFS 左儿子，如此进行下去，每次交换都实时更新答案即可。
时间复杂度 \(n\sqrt{n}\log n\)
做法三：分块+01-trie
一个我自己 yy 出来的算法（
上面莫队的做法每次向右移动都要插入新的元素，复杂度就总要多一个 log，并且莫队移动复杂度本身就带个根号导致这个 log 不太好摊，因此考虑将莫队换成分块。我们考虑设一个阈值 \(B\) 然后每 \(B\) 个元素一块，在下文中方便起见，设 \(L_i,R_i\) 分别表示每一块的左右端点。那么对于每一块 \(i\)，我们设 \(v_{i,j}\) 表示这一块中所有 \(c_k\ne 0\) 的元素 \(k\) 的 \(k-j\) 的异或和，其中 \(j\) 小于第 \(i\) 块的左端点，那么每次查询就整块调用预处理求得的值，散块暴力即可。那么怎么求 \(v_{i,j}\) 呢？我们考虑将这一块中所有 \(c_k\ne 0\) 的 \(k\) 的 \(k-L_i+1\) 插入 01-trie，然后从 \(L_i-1\) 开始往前遍历，每次进行全局 \(+1\) 操作，那么每次 \(+1\) 后得到的异或和就分别是我们要求的 \(v_{i,L_i-1},v_{i,L_i-2},\cdots\)。
显然取 \(B=\sqrt{n\log n}\) 时复杂度最优。
时间复杂度 \(n\sqrt{n\log n}\)
const int MAXN=2e5;
const int BLK=300;
const int MAXP=1e5;
const int LOG_N=20;
int n,m,qu,cnt[MAXN+5],v[BLK+5][MAXN+5];
int bel[MAXN+5],L[BLK+5],R[BLK+5];
int ch[MAXP+5][2],siz[MAXP+5],ncnt=0,rt=0,val[MAXP+5];
void clear(){
memset(ch,0,sizeof(ch));ncnt=rt=0;
memset(siz,0,sizeof(siz));memset(val,0,sizeof(val));
}
void pushup(int k,int d){val[k]=val[ch[k][0]]^val[ch[k][1]]^((siz[ch[k][1]]&1)?(1<<d):0);}
void insert(int &k,int v,int d){
if(!k) k=++ncnt;siz[k]++;if(d==LOG_N) return;
insert(ch[k][v>>d&1],v,d+1);pushup(k,d);
}
void add1(int k,int d){
if(!k) return;swap(ch[k][0],ch[k][1]);
add1(ch[k][0],d+1);pushup(k,d);
}
int query(int l,int r){
if(bel[l]==bel[r]){
int res=0;
for(int i=l;i<=r;i++) if(cnt[i]) res^=(i-l);
return res;
} else {
int res=0;
for(int i=l;i<=R[bel[l]];i++) if(cnt[i]) res^=(i-l);
for(int i=L[bel[r]];i<=r;i++) if(cnt[i]) res^=(i-l);
for(int i=bel[l]+1;i<bel[r];i++) res^=v[i][l];
return res;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,x;i<=n;i++) scanf("%d",&x),cnt[x]^=1;
int blk_sz=max((int)sqrt(m*log2(m)),1),blk_cnt=(m-1)/blk_sz+1;
for(int i=1;i<=blk_cnt;i++){
L[i]=(i-1)*blk_sz+1;R[i]=min(i*blk_sz,m);
for(int j=L[i];j<=R[i];j++) bel[j]=i;
clear();
for(int j=L[i];j<=R[i];j++) if(cnt[j]) insert(rt,j-L[i],0);
for(int j=L[i]-1;j;j--) add1(rt,0),v[i][j]=val[rt];
} int qu;scanf("%d",&qu);
while(qu--){
int l,r;scanf("%d%d",&l,&r);
printf("%s",(query(l,r))?"A":"B");
}
return 0;
}
做法四：根分+BIT
这是官方题解的做法（
考虑设一个阈值 \(K\) 并将询问离线下来。那么我们将所有位分为 \(<2^K\) 的位和 \(\ge 2^K\) 的位，对于 \(<2^K\) 的位就暴力存下所有数对 \(2^K\) 取模的值，查询时用个桶维护一下即可。对于 \(\ge 2^K\) 的位我们考虑扫描线，将询问挂在左端点处，可以注意到随着左端点的增大，每个 \(c_i-l\) 的 \(\ge 2^K\) 的位最多变化 \(\dfrac{m}{2^K}\) 次。我们就用 BIT 维护这些 \(c_i-l\) 的 \(\ge 2^K\) 位的异或值即可。取 \(K=\log_2(n\log n)\) 时复杂度最优。
时间复杂度 \(n\sqrt{n\log n}\)
有本事强制在线啊
做法 499122181：根分+分块
根据根号平衡的思想，我们把上面做法中 BIT 换成 \(\mathcal O(1)\) 单点加，\(\mathcal O(\sqrt{n})\) 求异或和的分块即可实现 \(n\sqrt{n}\) 的复杂度。
u1s1 官方题解为啥没想到根号平衡啊，不太懂
做法五：倍增
这是一个 nb 至极的倍增做法，不仅可以强制在线，而且复杂度还是 \(n\log n\) 的 %%%%%%%%
由于倍增本就基于二进制，而这题恰好涉及与下标有关的二进制运算，因此我们应尝试往倍增的方向考虑。我们设 \(f_{i,j}=\oplus_{c_k\in[j,j+2^i-1]}(c_k-j)\)。首先考虑怎么求 \(f_{i,j}\)：考虑首先拿 \(f_{i-1,j}\) 去异或 \(f_{i-1,j+2^{i-1}}\)，那么显然这两个东西异或在一起恰好包含了 \(2^0\sim 2^{i-2}\) 位的所有贡献，而显然 \(2^{i-1}\) 位会产生贡献，当且仅当有奇数个 \(c_k\in[j+2^{i-1},j+2^i)\)，因此我们可以得到以下转移方程：
f[i][j]=f[i-1][j]^f[i-1][j+(1<<i-1)]^(((a[j+(1<<i)-1]-a[j+(1<<i-1)-1])&1)<<i-1);
其中 \(a\) 为桶的前缀和。
得出了 \(f\) 数组之后求解答案就非常 easy 了，考虑从大到小遍历每一位 \(i\)，如果 \(l+2^i-1\le r\) 那么我们就将答案异或上 \(f_{i,l}\)，即将 \([l,l+2^i-1]\) 的贡献计入答案，同时对于 \(c_k\in[l+2^i,r]\)，它们也应对答案产生 \(2^i\) 的贡献，额外加上即可。
时间复杂度 \(n\log n\)。
const int LOG_N=18;
const int MAXN=2e5;
int n,m,qu,a[MAXN+5],f[LOG_N+2][MAXN+5];
int main(){
scanf("%d%d",&n,&m);
for(int i=1,x;i<=n;i++) scanf("%d",&x),a[x]++;
for(int i=1;i<=m;i++) a[i]+=a[i-1];
for(int i=1;i<=LOG_N;i++) for(int j=1;j+(1<<i)-1<=m;j++)
f[i][j]=f[i-1][j]^f[i-1][j+(1<<i-1)]^(((a[j+(1<<i)-1]-a[j+(1<<i-1)-1])&1)<<i-1);
scanf("%d",&qu);while(qu--){
int l,r,cur,res=0;scanf("%d%d",&l,&r);cur=l;
for(int i=LOG_N;~i;i--){
if(r-cur+1>=(1<<i)) res^=f[i][cur],cur+=(1<<i),res^=((a[r]-a[cur-1])&1)<<i;
} printf("%s",(res)?"A":"B");
}
return 0;
}