棋盘上的棋子：题解

思路

裁剪后，位于列 $x$ 的棋子是大小为 $x-L$ 的 Nim 堆。因此 Bob 获胜当且仅当

同一列出现偶数次会在异或中抵消。

做法

子任务 1：逐询问扫描

对每个询问扫描全部棋子并直接异或，复杂度 $O(nq)$。

子任务 2：枚举区间

固定左端点 $L$，从左到右加入各列；若该列棋子数为奇数，就异或 $R-L$。预处理所有 $O(m^2)$ 个区间后常数回答。

满分算法

令 $f_{k,L}$ 表示长度 $2^k$ 的区间 $[L,L+2^k-1]$ 内所有棋子相对 $L$ 的异或。合并两半时，右半每个堆增加 $2^{k-1}$；若右半棋子数为奇数，就额外异或这一位。

回答询问时从高位到低位把 $[L,R]$ 分成二进制块。加入长度 $2^k$ 的块后，尚未加入的所有堆相对原左端点都多出这一位；若剩余棋子数为奇数，同样异或 $2^k$。前缀计数可常数判断奇偶。

复杂度

三种算法分别为 $O(nq)$、$O(m^2+q)$、$O((m+q)\log m+n)$；满分算法空间为 $O(m\log m)$。