T1 生命游戏（gol）

注意到只有 $2^{4\times 4}$ 种输入，我们可以先枚举每种输入确立其下一个状态，然后倍增或者通过内向树处理都是可以的。

时间复杂度 $\Theta(states\log T + Q\log T)$ 或者 $\Theta(states + Q)$。

T2 装备升级（upgrade）

性质 A

我们容易发现这样一个事实：不可能有两个装备恰好是一级，否则一定可以将一个升级挪到另一个上。

因此可以导出这一性质：

• 若 $m$ 是偶数，那么一定是选 $w_1 + w_2$ 前 $m/2$ 小的。

• 若 $m$ 是奇数，那么要么是选前 $\lfloor m/2\rfloor$ 小的 $w_1+w_2$，再在剩下的里面选一个一级，要么是选前 $\lceil m/2\rceil$ 小的 $w_1+w_2$，再在这些里面退掉一个二级。

因此我们先按照 $w_1+w_2$ 排序，然后枚举就可以了。

性质 B

我们考虑贪心选取最小的 $m$ 个 $w$，不难发现他们一定是可以满足要求的。因此只需一次 $\texttt{nth_element}$，可以做到 $\Theta(n)$。

std

我们考虑 $w_1\le w_2$ 和 $w_1>w_2$ 已经涵盖了所有可能性，我们考虑对于两拨分别算出所有 $m$ 的答案，之后枚举一边实际选了几个就可以了。

对于性质 A，我们可以用前后缀 $\min$ 来加速，对于性质 B，我们只需要排序之后做一遍前缀和即可。

因此总共复杂度瓶颈为排序，$\Theta(sort(n))$。

T3 因子统计（divisor）

我们注意到如果一个数的质因子分解是 $p_1^{k_1} \cdots p_n^{k_n}$，那么因子数量就是 $(k_1+1)\cdots (k_n+1)$。

std

考虑一个莫队，我们在 $(n,m)$ 的移动过程中维护 $\binom n m$ 的质因子分解中 $> \sqrt n$ 的那部分，这样每次移动只会有 $\Theta(1)$ 个质因子增减。最后统一统计 $\le \sqrt n$ 的质因子贡献，因为总共只有 $\pi(\sqrt n) = \Theta \left( \frac{\sqrt n}{\log n}\right)$ 个质数，我们每个质数暴力做就是 $\Theta(\sqrt n)$ 的了。复杂度是 $\Theta(q\sqrt n + n\sqrt q)$。

bonus

本题可以做到……的复杂度？