chx记录一个很有意思的观察。朴素的博弈 DP 状态是
$$DP[i,j]:=位置在\ i\ 并且能力为\ j\ 的前提下先手是否必胜\def\la#1{\langle #1\rangle}$$然后转移就是
$$\begin{align*} DP[i,j]&=1\\ &\leftrightarrow (\exists x:j\le x\le j+a[i])(\exists y:i<y\le i+x)\la{DP[y,x]=0} \end{align*}$$我们可以通过记录满足 $\la{DP[y,x]=0}$ 最小的 $y$ 来压缩掉对 $y$ 的枚举，即令
$$f[x]:=(\mu y)\la{DP[y,x]=0}$$那么显然我们有
$$\begin{align*} DP[i,j]&=1\\ &\leftrightarrow (\exists x:j\le x\le j+a[i])\la{f[x]\le x+i} \end{align*}$$相对，我们要去维护 $f$ ，由于我们的 $f$ 是一个相对的值，并且我们的状态 $i$ 是从大到小更新的，所以我们只在每次更新 $DP[i,j]\leftarrow 0$ 的时候更新 $f[j]\leftarrow i$ 。整个过程可以理解为在从大到小遍历 $i$ 的时候如果 $f[x]-x>i$ 我们就把 $x$ 加入线段，之后我们用一个数据结构维护连续的线段，一旦某个连续的线段的长度超过 $a[i]+1$ 就可以更新了。
之后剩下的问题是怎么高效地更新，答案是暴力就可以了，以下的观察解释了这一点
如果 $f[x]$ 在 $i$ 处被更新，那么下一次 $f[x]$ 更新至多为 $i-x$
于是总的来看 $f[x]$ 被更新的次数不超过 $O\left(\frac nx\right)$ ，因此总的更新次数不超过
$$\begin{align*} &O\left(\frac n1\right)+O\left(\frac n2\right)+...+O\left(\frac nn\right)\\ \sim& O\left(n\log n\right) \end{align*}$$维护连续段的事情可以交给线段树或者 set 。