好难好难好难。
首先自己的防火墙竟然是别人操控的。好难受，我们更换一下游戏定义：
两个人，每个人有能量、金币
Xi=(Ai,Bi)。两个人轮流操作，每一轮可以选择以下两个操作之一：
- 让对方能量降低 A；
- 花费 1 金币让血量上升 S。
一个人死亡当且仅当
A+BS≤0。问谁赢。
容易写一个
f(A0,B0,A1,B1) 的表示谁赢。直接搜。复杂度有点抱抱抱。
【性质 1】 如果
f(X0,X1) 为真，那么让
A0/B0 增加仍未真。
f(X0,X1) 为假那么让
A0/B0 减少仍然为假。
我们来说明，我们只需要关注
A0,A1∈(0,S) 的博弈。其余的博弈都是唯一转移的，假设现在是
0 的回合：
- 当 A0≤0 时只能选择 2 操作；
- 当 A1≥S 时，必须选择 2。因为如果选择 2，那么对方打你你的血量会更低，而对让血量不变，违反性质 1。（【性质 2】）
- 当 A0≥S≥A1 时，0 必胜。因为每次 0 发动攻击 1 回血回不回来，只能乖乖挨打。
- 当 A1≤0≤A0 时如果 B0>0 就会选择 2，这时候会回到情况 2。
至此我们讨论了所有
A0∈(0,S) 或者
A1∈(0,S) 的情况。都是唯一转移的，而且容易快速转至
A0,A1∈(0,S) 的情况。
注意到
A0+SB0≤V。这里直接记搜复杂度是
O(S2logS) 的。
能不能再给力一点！考虑
A0,A1∈(0,S) 的情况。如果 0 选择 2 操作，根据【性质 2】，对方必须选择打。于是我们把 1 操作变成了让自己血量上升
S−A1 的操作。
如果
A0+B0(S−A1)≥S 了。那么我肯定先把自己的金币全买完，然后给对方致命一击。
否则，我们就会交出先手权。假设交出先手权前买了
x 次名。为了对方不能 All in 然后秒杀自己，你需要保证：
最终会解得
x≥(B1+1)(S−A1)A1+(B1−1)S−A0(B1+1)=k。那么我们就先买
k 次命再继续搜。状态数少了很多。
此时
(A0,B0,A1,B1) 状态数仍然很多。由于有单调性（性质 1），我们可以把一维干掉。我们尝试把
A0 干掉，我们接下来尽可能减少
(B0,A1,B1) 的状态数。
经过我们上面讨论，我们现在观察的
(A0,B0,A1,B1) 是当前你秒不掉对方，交出先手权之后对方秒不掉你。
我们观察一下什么情况对方交出先手权之后你就能秒掉对方。由于我们需要把
A0 干掉，我们令
A0=0。
首先假设我们第一轮买了
x 次名。此时
A0′=x(S−A1)。
然后第二轮对方为了制止你交回去之后把它秒了，肯定会 All in，即
A1′=A1−A0′+B1(S−A0′)。
然后我们第三轮直接 All in，
A0′′=A0′−A1′+(B0−x)(S−A1′)。
然后你要解出
A0′′≥S 这样子就秒掉了。我们只需要
(B0−x)(S−A1′)≥2S。
展开，带上一定放缩得到
(B0−x)x(B1−1)(S−A1)≥2S，即
B02(B1−1)(S−A1)≥8S 即可。
所以如果
B02(B1−1)(S−A1)>8S，无论
A0 如何 0 都是必胜的。
反之，这样的
(B0,B1,A1) 的个数是
∑i2SlnS 的，即
O(SlogS) 的。对每个这种对二分找出最小的
A0 使得 0 为胜者。每次查询一个状态需要查询 map。
总的复杂度就是
O(Slog3S+qlogS) 的。