G. 棋盘上的芯片
时间限制：$5$ 秒
内存限制：$512$ MB

Alice 和 Bob 有一个 $n$ 行 $m$ 列的矩形棋盘，每行恰好有一个芯片。
他们选择 $l$ 和 $r$（$1 \le l \le r \le m$），裁剪棋盘保留第 $l$ 列到第 $r$ 列的部分。
然后两人轮流移动芯片，每次可以选择一个芯片向左移动任意正整数格（不能移出棋盘）。
无法移动者输。

给出 $q$ 个询问 $(L_i, R_i)$，对于每个询问，若 $l = L_i$，$r = R_i$，问先手（Alice）是否获胜。

---

博弈论转化

这是一个 impartial combinatorial game。
每个芯片独立，整个游戏是这些独立游戏的 Nim 和。
第 $i$ 行的芯片在保留 $[L,R]$ 时，可移动步数为 $c_i - L$（若 $c_i \ge L$），否则不在棋盘上。
因此，Nim 堆大小为 $c_i - L$。

根据 Nim 理论，先手获胜当且仅当所有堆大小的异或和不为 0。
定义：

$$X(L,R) = \bigoplus_{i: L \le c_i \le R} (c_i - L)$$

若 $X(L,R) = 0$ 则 Bob 胜（输出 B），否则 Alice 胜（输出 A）。

---

核心思路

我们需要对 $q$ 个询问快速计算 $X(L,R)$。
每个 $c_i - L$ 最多 $B = \lceil \log_2 m \rceil$ 位（$m \le 2\times 10^5$，$B \le 18$）。

官方解法采用根号分治：
选择一个 $K$，用不同方法处理低 $K$ 位和高 $B-K$ 位。

---

统一框架：将询问拆成两个前缀查询

定义：

$$Q(x,y) = \bigoplus_{c_j \ge x} (c_j - y)$$

那么：

$$X(L,R) = Q(L, L) \oplus Q(R+1, L)$$

证明：
$c_j$ 在 $[L,R]$ 内当且仅当 $c_j \ge L$ 且 $c_j \ge R+1$ 不成立，因此异或中 $[L,R]$ 内的贡献出现一次，$[R+1, m]$ 内的贡献出现两次（抵消），故上式成立。

这样，每个询问拆成两个形式为 $Q(x,y)$ 的子问题，其中 $x$ 是某个左端点（$L$ 或 $R+1$），$y$ 是原询问的 $L$。

我们将所有 $Q(x,y)$ 按 $x$ 分组，然后从大到小扫描 $x$（$x = m$ 到 $1$），维护当前已处理的 $c_j \ge x$ 的芯片信息，对于每个 $x$ 回答所有 $Q(x,y)$ 的查询。

---

处理低 $K$ 位

我们只关心 $c_j - y$ 的低 $K$ 位（模 $2^K$ 的值）。
由于模 $2^K$，$c_j$ 和 $y$ 都只需考虑其模 $2^K$ 的余数。
不同余数最多 $2^K$ 种。

在扫描 $x$ 的过程中，维护一个数组 rem[0..2^K-1]，rem[z] 表示当前已处理的芯片中，$c_j \bmod 2^K = z$ 的芯片个数的奇偶性（因为异或只需要奇偶性）。

对于查询 $Q(x,y)$，我们枚举所有可能的余数 $z$，若 rem[z] 为奇数，则异或上 $(z - y \bmod 2^K)$（模 $2^K$ 取正）。
枚举量 $O(2^K)$ 每个查询。

复杂度：$O(n + m + q \cdot 2^K)$。

---

处理高 $B-K$ 位

高 $B-K$ 位是 $(c_j - y) \gg K$ 的值。
观察：当 $x$ 从 $m$ 下降到 $1$ 时，对固定的 $c_j$，$c_j - x$ 的高位只在 $x$ 跨越某些边界时改变一次。
实际上，每 $2^K$ 个数为一段，高位相同。

具体来说，对于每个 $c_j$，考虑区间 $[l, r]$，其中 $l = \max(1, c_j - t \cdot 2^K + 1)$，$r = c_j - (t-1) \cdot 2^K$，$t \ge 1$，且 $l \le r$。
对于该区间内的 $x$，$c_j - x$ 的高位为 $t-1$（或 $t$ 取决于具体定义，这里我们取 $(c_j - x) \gg K$）。

因此，在扫描 $x$ 时，当 $x$ 进入某个区间 $[l, r]$，我们需要将高位值 $t-1$ 异或到所有以 $x$ 为左端点的查询 $Q(x,y)$ 的答案中（注意这里的 $x$ 是扫描变量，$y$ 是查询的第二个参数）。

为了实现这一点，我们维护一个支持区间异或、单点查询的数据结构（如 Fenwick 树，用异或代替加法）。
具体操作：

• 对每个芯片 $c_j$，将其覆盖的 $O(m / 2^K)$ 个区间 $[l, r]$，执行：
  • change(l, diff)（区间 $[l, m]$ 异或上 diff）
  • change(r+1, diff)（区间 $[r+1, m]$ 再异或上 diff，实现区间 $[l, r]$ 的异或）
• 对于查询 $Q(x,y)$，直接 get(y) 得到所有芯片对该查询的高位贡献的异或和。

复杂度：

• 每个芯片更新 $O(m / 2^K)$ 次，每次 $O(\log m)$，总 $O(n \cdot m / 2^K \cdot \log m)$。
• 每个询问查询一次，$O(q \log m)$。

---

参数选择

总复杂度为：

$$O\left(n + m + q \cdot 2^K + n \cdot \frac{m}{2^K} \log m + q \log m\right) $$

令 $N = \max(n, m, q)$，$B \approx \log_2 m$，则 $2^K$ 和 $m/2^K$ 平衡时，$2^K \approx \sqrt{m}$。
由于 $m \le 2\times 10^5$，$\sqrt{m} \approx 447$，但 $K$ 取 $10$ 时 $2^K = 1024$，仍可接受。

最终复杂度 $O(N \sqrt{N \log N})$。

---

代码解析

const int N = 200043;
const int K = 10;
const int Z = 1 << K;  // Z = 1024

• rem[Z]：记录每个余数模 $Z$ 的奇偶性。
• t[N]：Fenwick 树（异或树），维护高位贡献。
• change(l, diff)：将区间 $[l, m]$ 异或上 diff。
• get(r)：返回 $[0, r]$ 的异或和。
• qs[x]：以 $x$ 为左端点的查询编号（对应 $Q(x, L)$）。
• qs2[x]：以 $x$ 为右端点 $+1$ 的查询编号（对应 $Q(x, L)$，但 $x = R+1$）。

主循环：

for (int i = m; i >= 1; i--) {
    // 处理所有在列 i 的芯片
    for (int j = 0; j < cnt[i]; j++) {
        rem[i % Z]++;  // 更新低位余数奇偶性

        // 处理该芯片的高位区间更新
        int r = i;
        while (true) {
            int l = r - Z + 1;
            l = max(1, l);
            if (l > r) break;
            int diff = (i - l) >> K;  // 高位值
            change(l, diff);
            change(r + 1, diff);
            r -= Z;
        }
    }

    // 回答 Q(i, L) 形式的查询（即左端点 = i）
    for (auto x : qs[i]) {
        int cur = (get(i)) << K;  // 高位部分左移 K 位
        // 低位部分枚举所有余数
        for (int k = 0; k < Z; k++) {
            int dist = (k - i) % Z;
            if (dist < 0) dist += Z;
            if (rem[k] & 1) cur ^= dist;
        }
        ans[x] ^= cur;
    }

    // 回答 Q(i, L) 形式的查询（其中 i = R+1）
    for (auto x : qs2[i]) {
        int cur = (get(ls[x])) << K;
        for (int k = 0; k < Z; k++) {
            int dist = (k - ls[x]) % Z;
            if (dist < 0) dist += Z;
            if (rem[k] & 1) cur ^= dist;
        }
        ans[x] ^= cur;
    }
}

注意：

• get(i) 返回的是当前所有芯片对查询位置 $i$ 的高位贡献异或和。
• 低位部分直接枚举余数，用 rem[k] & 1 判断奇偶。
• cur 是 $Q(x,y)$ 的完整值（高位 $<<K$ 后与低位异或），最终异或到 ans[x] 中。

---

最终输出

for (int i = 0; i < q; i++)
    if (ans[i] == 0) printf("B");
    else printf("A");

若 $X(L,R) = 0$ 则 Bob 胜，否则 Alice 胜。

---

总结

这道题通过根号分治处理不同二进制位，结合离线扫描、Fenwick 树区间异或和枚举余数，在 $O(N \sqrt{N \log N})$ 时间内解决了 $q$ 个 Nim 游戏询问。
代码中 $K=10$ 是经验选择，平衡了低位枚举与高位分段更新的复杂度。