不难发现这是个 Nim 游戏，于是对每对 \((L_i, R_i)\) 所求转化为：
\[\bigoplus_{i = 1}^n (a_i - L_i)[a_i \ge L_i]
\]
暴力做时间复杂度就是 \(\mathcal O(n^2)\)，考虑优化。
感觉好像可以倍增？设 \(f(i, k)\) 表示 \([i, i + 2^k)\) 内 \(a_j - i\) 的异或和，然后再记一个 \(g(i, k)\) 表示 \([i, i + 2^k)\) 内棋子的个数就很妙地可以转移了。时间复杂度 \(\mathcal O(n \log n)\)。
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 2e5 + 10, K = 19;
int n, m, a[N], f[N][K], g[N][K];
int main() {
ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i], g[a[i]][0]++;
for (int k = 1; k < K; k++) {
for (int i = 1; i + (1 << k) - 1 <= m; i++) {
g[i][k] = g[i][k - 1] + g[i + (1 << (k - 1))][k - 1];
f[i][k] = f[i][k - 1] ^ f[i + (1 << (k - 1))][k - 1];
if (g[i + (1 << (k - 1))][k - 1] & 1) f[i][k] ^= (1 << (k - 1));
}
}
int q; cin >> q;
while (q--) {
int l, r; cin >> l >> r;
int ans = 0, tmp = 0;
for (int k = K - 1; k >= 0; k--) {
if (l + (1 << k) - 1 <= r) {
ans ^= f[l][k];
if (g[l][k] & 1) ans ^= tmp;
tmp ^= (1 << k);
l += (1 << k);
}
}
ans ? cout << 'A' : cout << 'B';
}
return 0;
}