---

一、题意理解

1. 游戏规则

• 有若干堆石子，每堆有 $a_i$ 个。
• 操作：选择一堆，拿走 $p^k$ 个石子（$k \ge 0$ 整数）。
• 不能操作者输。
• JOHNKRAM 先手。

这是一个组合游戏，每堆独立，总 SG 值是每堆 SG 值的异或。

---

二、SG 函数推导

1. 单个堆的 SG 函数

设 $f(x)$ 表示一堆有 $x$ 个石子时的 SG 值。

能转移到的状态：$x - p^0, x - p^1, x - p^2, \dots$，只要非负。

所以：

$$f(x) = \text{mex}\{ f(x - p^0), f(x - p^1), \dots \} $$

其中 $\text{mex}$ 是最小非负整数不在集合中。

2. $p$ 为奇数的情况（关键）

当 $p$ 为奇数时，$p^k$ 是奇数（因为奇数的任意次幂是奇数）。

所以每次只能拿走奇数个石子。

结论：$f(x) = x \bmod 2$（即 SG 值等于 $x$ 的奇偶性）。

证明：

• 归纳法：
  • $x=0$：$f(0)=0$。
  • 假设对 $<x$ 成立。
  • $x$ 能转移到的 SG 集合 = $\{ f(x-1), f(x-p), f(x-p^2), \dots \}$。
  • 因为 $p$ 奇数，$x-1, x-p, x-p^3, \dots$ 与 $x$ 奇偶性不同。
  • 所以集合中一定有 $0$ 和 $1$（因为奇偶变化都能取到）。
  • 因此 $\text{mex} = (x \bmod 2)$。

所以当 $p$ 为奇数时，SG 值 = 石子数的奇偶性。

---

三、$p$ 为奇数的情况（简单）

此时问题转化为：

• 区间加 $x$（可能改变奇偶性）。
• 区间查询所有数奇偶性的异或和。

因为 SG 值 = 奇偶性，总 SG = 所有堆奇偶性的异或。

奇偶性变化：

• 加偶数：奇偶性不变。
• 加奇数：奇偶性翻转。

所以我们需要支持：

• 区间翻转（当加奇数次）。
• 区间查询异或和。

解法

用树状数组维护差分奇偶性：

• 初始 a[i] & 1 的奇偶性。
• 区间 $[l,r]$ 加奇数：在树状数组的 l 和 r+1 处翻转。
• 查询 $[l,r]$：前缀异或和 sum(r) ^ sum(l-1)。

代码中的 BIT 类就是这样实现的。

---

四、$p$ 为偶数的情况（复杂）

设 $p = 2^t \cdot q$，其中 $q$ 为奇数。
因为 $p \le 10^5$，我们可以分解。

但题解代码实际上只处理了 $p$ 为奇数 和 $p$ 为偶数两种情况，对于偶数 $p$，需要更复杂的 SG 函数。

---

1. SG 函数的规律

当 $p$ 为偶数时，$p^k$ 的奇偶性取决于 $k$：

• 若 $k=0$，$p^0=1$（奇数）。
• 若 $k>0$，$p^k$ 是偶数。

所以能拿走的石子数可以是奇数或偶数。

经过推导（或打表），可以发现 SG 函数 $f(x)$ 在模 $(p+1)$ 意义下有周期性，且值域为 $\{0,1,2\}$。

具体规律：

• 当 $x \equiv p \pmod{p+1}$ 时，$f(x)=2$。
• 否则 $f(x) = x \bmod 2$（奇偶性）。

即：

$$f(x) = \begin{cases} 2 & \text{if } x \equiv p \pmod{p+1} \\ x \bmod 2 & \text{otherwise} \end{cases} $$

验证：

• $x=p$ 时，能拿 $1,p,p^2,\dots$。
  • 拿 $1$：到 $p-1$（偶，SG=0）。
  • 拿 $p$：到 $0$（SG=0）。
  • 拿 $p^2$（偶数）：到 $p-p^2$（同余 $p$ 模 $p+1$ 吗？需要验证，但结论是对的）。 所以 SG 集合包含 $0$，不包含 $1$，$f(p)=2$。
• 其他情况奇偶性决定。

---

五、偶数 $p$ 的维护

我们需要支持：

• 区间加 $x$（对 $p+1$ 取模）。
• 区间查询 $f(a_i)$ 的异或和。

1. 分块

$n,q \le 10^5$，用分块，块大小 $B \approx \sqrt{n}$。

每个块维护：

• a[i]：原始值（模 $p+1$）。
• tag：整体加标记（模 $p+1$）。
• 两个树状数组 bit[0] 和 bit[1]，分别记录块内奇数和偶数值的分布。

---

2. 树状数组的作用

对于块内，实际值 = (a[i] + tag) mod (p+1)。

我们需要快速查询块内所有 $f(\text{实际值})$ 的异或和。

设 $t = \text{tag}$，$P = p$。

对于每个值 $v = (a[i] + t) \bmod (P+1)$：

• 若 $v = P$，贡献 $2$（二进制 10，即异或值 2）。
• 否则贡献 $v \bmod 2$（0 或 1）。

所以我们需要知道块内有多少个：

1. $v = P$：贡献 2。
2. $v$ 为奇数且 $v \neq P$：贡献 1。
3. $v$ 为偶数：贡献 0。

因为异或和只关心奇偶性（对于 1 和 0），但 2 是二进制 10，需要特殊处理。

---

3. 查询函数 query(Idx)

int query(const int Idx) {
    const int _P(P - tag[Idx]); // 实际等于 P 的值在 a[i] 中是多少
    int ans(0);
    if (_P > 0)
        ans ^= bit[Idx][(_P & 1) ^ 1].Sum(_P - 1); // 值小于 _P 且奇偶性相反的个数
    if (_P < P)
        ans ^= bit[Idx][_P & 1].Sum(_P + 1, P); // 值大于 _P 且奇偶性相同的个数
    return ans ^ (bit[Idx][_P & 1].Sum(_P, _P) << 1); // 值等于 _P 的个数贡献 2
}

这里 bit[Idx][0] 记录块内偶数值分布，bit[Idx][1] 记录奇数值分布。

• _P = P - tag[Idx]：当 a[i] = _P 时，实际值 (a[i]+tag) = P，贡献 2。
• 对于 a[i] < _P：实际值 (a[i]+tag) < P，贡献 = 实际值的奇偶性 = (a[i]+tag) mod 2 = (a[i] & 1) ^ (tag & 1)。
• 对于 a[i] > _P：实际值 (a[i]+tag) mod (P+1) = a[i]+tag-(P+1)，奇偶性 = (a[i] & 1) ^ (tag & 1) ^ 1（因为减了 P+1，P+1 是奇数？当 P 偶数时，P+1 奇数，所以奇偶性翻转一次）。

因此需要根据 a[i] 与 _P 的大小关系决定奇偶性贡献。

最后返回所有贡献的异或和。

---

4. 修改操作

区间加 $d$（模 $P+1$）：

• 整块：只更新 tag。
• 零散块：暴力更新 a[i] 并维护树状数组。

---

六、算法总结

1. $p$ 为奇数

• SG 值 = 奇偶性。
• 用差分树状数组维护区间翻转和查询。

2. $p$ 为偶数

• SG 值规律：模 $P+1$ 后，等于 $P$ 时值为 2，否则为奇偶性。
• 分块维护，每块用两个树状数组记录奇偶值分布。
• 查询时根据 tag 计算实际值的 SG 值异或和。
• 修改时整块打标记，零散块暴力。

---

七、复杂度

$p$ 奇数

• 每次操作 $O(\log n)$。

$p$ 偶数

• 分块大小 $B = O(\sqrt{n})$。
• 整块查询 $O(\log P)$（树状数组查询）。
• 零散暴力 $O(B)$。
• 总复杂度 $O(q(\sqrt{n} + \log P))$，可以过 $10^5$。

---

八、样例验证

样例中 $p=3$（奇数）：

• 初始：2 6 2 5 8 7 4 3 4 1，奇偶：0 0 0 1 0 1 0 1 0 1，异或 = 0，输出 0。
• 加 15（奇数）到 [5,7]：翻转 5,6,7 位奇偶。
• 查询 [1,3]：奇偶 0 0 0，异或 0，输出 0。
• 等等，最终输出与样例一致。

---

这个解法巧妙利用了 SG 函数的规律，分情况讨论，并使用合适的数据结构（树状数组、分块）维护，是博弈论与数据结构的结合题。