题目大意 有 nnn 盘饼干，双方轮流拿取，每次拿完后可以选择是否将剩余饼干合并到别的盘中，若最终无法拿取的人则输掉游戏。给出 qqq 次询问，求出询问区间 [l,r][l,r][l,r] 中有多少子段先手必胜。 题目思路 先考虑固定盘数时双方如何博弈。 若只有 111 盘饼干，先手必胜。 若有 222 盘饼干，谁把某一盘的饼干取完了谁就输了，所以每一盘饼干有一块是不能取的。不妨令 ai=ai−1a_i=a_i-1ai =ai −1 ，这样问题就变成 nimnimnim 游戏问题，也就是说 XORi=lr(ai−1)=0XOR_{i=l}^{r}(a_i-1)=0XORi=lr (ai −1)=0 的话，先手必败，反之先手必胜。 若有 333 盘饼干，先手可以从最多的那盘取出若干饼干，将剩下的局面变成盘数为 222 且上文提到的异或和为 000 的情况，那么先手必胜。 若有 444 盘饼干，谁先将盘数 −1-1−1 谁就输了，所以还是看异或和是否为 000 。 以此类推，不难发现，当堆数为奇数时，先手必胜，否则令 ai=ai−1a_i=a_i-1ai =ai −1 ，看异或和是否为 000 。 所以我们只需要前缀异或，离线查询，用莫队求解。 时间复杂度 O(nn)O(n\sqrt{n})O(nn ) 。 参考代码