通过 Nim 定理，很容易发现第 $i$ 个询问的答案是 B 当且仅当 $igopluslimits_{L_i le c_j le R_i}(c_j - L_i) = 0$。否则询问的答案就是 A。
那么我们来对每一个询问计算这个异或和。发现答案 $<2^{18}$，接下来尝试根号分治，选择某一个数 $K$，用一种算法去计算最低的 $K$ 位的答案，用另一种算法去计算最高的 $18-K$ 位的答案。
两种算法都有一个共同的思想：我们会把每一个询问拆成两个询问：$(L_i, R_i)$ 会被表示为 $Q(L_i, L_i)$ 和 $Q(R_i + 1, L_i)$，这里 $Q(x, y) = igopluslimits_{c_j ge x}(c_j - y)$。其实本质就是一个差分。
在改造了询问之后，对于每一个 $x in [1, m]$，把每一个 $Q(x, y)$ 存在一些 vector 中。接着遍历 $x$，处理所有对于当前 $x$ 的询问。
怎么找到每个询问的最低 $K$ 位呢？从 $m o 1$ 遍历 $x$，用桶维护当前所访问过的每一个数字 $c_i$ 的数量。某时间我们想要计算 $Q(x, y)$，就遍历每一个桶，暴力计算它们的异或和。因为我们只关心答案的末 $K$ 位，所以只需要保留 $c_i mod 2^K$，所以计算异或和是 $O(2^K)$ 的，这一部分的时间复杂度是 $O(n+m+2^K q)$。
怎么找到每个询问的最高 $18-K$ 位呢？可以发现，对于每一个数字 $c_i$，在我们遍历 $x$ 的过程中，$c_i - x$ 的这些高位的变化并不频繁：$c_i - x$ 的这些位的变化只有约 $frac{m}{2^K}$ 个区间（这很好理解，因为我们不关心 $c_i - x$ 的末 $K$ 位，所以重复了 $2^K$ 次 $+1$ 后高位才会变化一次）。使用一种数据结构，支持两种操作：区间异或、单点查询。比如 BIT 就可以做到这件事。我们重新从 $m o 1$ 遍历 $x$，当我们想要处理一个数 $c_i$ 的时候，我们找到 $c_i - y$ 的高位相同的那些段区间，然后在 BIT 中更新这些区间。当查询 $Q(x, y)$ 的时候，直接查询 BIT 中 $y$ 位置的值即可。这部分的时间复杂度是 $O(n frac{m}{2^K} log m + m + q)$。
记 $N = max(n, m, q)$，在 $K$ 选定适当的情况下，可以在 $O(N sqrt{N log N})$ 的时间复杂度内解决这个问题。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, k = 10, K = 1 << 10;
int n, m, q, c[N], ans[N];
bool cnt[N], tub[K];
vector<pair<int, int>> vec[N]; // q[x] = {id, y}
struct binary_indexed_tree
{
int o[N];
void Modify(int p, int v)
{
for(; p <= m; p += (p & -p)) o[p] ^= v;
}
int Query(int p)
{
int res = 0;
for(; p; p -= (p & -p)) res ^= o[p];
return res;
}
} bit;
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
cin >> c[i];
cnt[c[i]] ^= 1;
}
cin >> q;
for(int i = 1; i <= q; i++)
{
int l, r;
cin >> l >> r;
vec[l].push_back(make_pair(i, l));
vec[r + 1].push_back(make_pair(i, l));
}
for(int i = m; i; i--)
{
if(cnt[i])
{
tub[i % K] ^= 1;
for(int r = i, l; r >= 1; r = l - 1)
{
l = max(1, r - K + 1);
bit.Modify(l, i - l >> k);
bit.Modify(r + 1, i - l >> k);
}
}
for(pair<int, int> qry : vec[i])
{
int res = bit.Query(qry.second) << k;
for(int j = 0; j < K; j++)
if(tub[j]) res ^= ((j - qry.second) % K + K) % K;
ans[qry.first] ^= res;
}
}
for(int i = 1; i <= q; i++) cout << "AB"[ans[i] == 0];
return 0;
}