题目大意
AB 博弈，给定 \(n\) 个正整数，每次选择一个 \(x\) ，将该数字变成 \(x-1\) ，然后使所有大于 \(x\) 的数字变成 \(x\) ，无法操作者输。
题解
题目操作的本质是：选择一个值 \(x\)，将其变为 \(x-1\)，然后把所有大于 \(x\) 的数削平到 \(x\)。
为了方便处理这种削平操作，我们将原数组降序排序，设为 \(h_1 \ge h_2 \ge \dots \ge h_n > 0\)。
并定义差分数组 \(d_i = h_i - h_{i+1}\)（其中 \(h_{n+1} = 0\)）。
当我们在原数组中选择了某个值 \(x\)（假设它对应降序数组中最后一次出现的位置是 \(k\)，即 \(h_k = x\) 且 \(d_k > 0\)），操作后的影响如下：
-
\(h_k \gets h_k - 1\)。
-
\(h_1 \dots h_{k-1}\) 原本大于或等于 \(x\)，全部被削平到 \(h_k\)。
反映在差分数组 \(d\) 上：
- \(d_k \gets d_k - 1\)
- \(d_{k-1} \gets 1\)
- \(d_1 \dots d_{k-2} \gets 0\)
观察上面的变化，你会发现一旦在 \(d_k\) 处进行操作，它会把 \(k-1\) 之前的所有状态强制覆盖。
这也就是说，操作 \(d_k\) 后得到的新状态，它的 SG 值完全且仅仅取决于 \(k\) 以及 \(k\) 后面的后缀 \((d_k, d_{k+1}, \dots)\)。
这里你会发现每个操作的后缀的 SG 值是固定的，这点很糖，你只需要从后缀递推一个集合 \(S\)，当前点的后继状态只有后缀集合和当前点权值 \(-1\)。
定义：\(m_0 = \text{mex}(S)\)，\(m_1 = \text{mex}(S \cup \{m_0\})\)，\(m_2 = \text{mex}(S \cup \{m_0, m_1\})\)。
设前缀仅第 \(j\) 位为 1 的状态 SG 值为 \(f_j\)。
显然有 \(f_j = \text{mex}(\{f_{j-1}\} \cup S)\)
易得规律：\(f_0=m_0, f_1=m_1, f_2=m_0 \dots\) 即 \(f_j = m_{j \bmod 2}\)。
操作 \(d_k\) 会在 \(k-1\) 处产生一个 1，因此状态递推的底边界为 \(f_{k-1}\)：
-
当 \(k\) 为奇数时：
\(k-1\) 为偶数，底边界为 \(f_{k-1} = m_0\)。
SG 值在 \(m_0, m_1\) 间交替 \(\implies\) \(d_k\) 奇数为 \(m_0\)，偶数为 \(m_1\)。
-
当 \(k\) 为偶数时：
\(k-1\) 为奇数，底边界为 \(f_{k-1} = m_1\)。
SG 值在 \(m_1, m_2\) 间交替 \(\implies\) \(d_k\) 奇数为 \(m_1\)，偶数为 \(m_2\)。
\(d_1\) 为奇数则全局 \(\text{SG} = m_1\)，偶数则 \(\text{SG} = m_0\)。
倒序遍历 \(d\)，用 std::set 动态维护 mex，时间复杂度 \(O(n \log n)\)。