[题解] [CF1434E] A Convex Game

给一个长为 $n$ 的单增序列 $v$，两人轮流选数，要求两人选出的数是 $v$ 的子序列且差分数组也单增，无法选的人输。求 SG 值。

$T$ 组询问。$1\le T\le 1000,1\le v_i,\sum n\le 10^5$。

---

我们有个结论，SG 值是 $O(\sqrt V)$ 的（事实上遇到这种有限状态上转移的游戏都应该想下这个）。证明：每次选出的差都要严格大于上一次的差，差的总和 $\le V$，于是一次游戏最多只能选根号个，而 SG 值是不大于最长转移次数的。

对于位置 $j$，我们分别对每种可能的 SG 值 $i$ 算出 $p_{i,j}$：如果要从这个位置开始然后得到 $i$ 这个 SG 值，最远可以跳到哪儿。考虑记一个 $pos_{i,j}$，代表我们现在选到了第 $j$ 个数，然后要使 选了下一个后 SG 值为 $i$，下一个最大能选到哪儿。于是就有
$$
p_{i,j}=\min_{0\le k<i}pos_{k,j}
$$
考虑转移，从右到左计算，对一个 $j$ 计算得到 $p_{i,j}$ 后我们就可以把前 $i-1$ 个数从左到右划成很多段，第一段转移过来的话 SG 值是 $1$，第二段转移过来 SG 值是 $2$，以此类推。我们就需要依次把这些段的 $pos_{i,k}$ 和我们当前的位置 $j$ 取 $\max$。那么怎么维护呢？开根号棵线段树？

其实我们发现由于我们是倒着枚举 $j$ 的，于是每个 $pos_{i,j}$ 只会被更新一次，于是我们用一个并查集做区间赋值即可。最后我们要算答案，只需要找到从每个位置开始的 SG 值然后取 $\mathrm{mex}$ 即可。

时间复杂度 $O(TV+n\sqrt V)$，但实际上没按秩合并的并查集复杂度不能算常数，但你考虑你不管那么多。

mivik.h / 代码