数论分块

$|D(n)|\le 2\sqrt{n}$．

分两种情况讨论：

• 当 $i\le \sqrt{n}$ 时，$i$ 的取值至多 $\sqrt{n}$ 个，所以 $\lfloor {\displaystyle \frac{n}{i}}\rfloor$ 的取值也至多只有 $\sqrt{n}$ 个．
• 当 时， 也至多只有 $\sqrt{n}$ 个取值．

因此，所有可能取值的总数 $|D(n)|\le 2\sqrt{n}$．

设 $s=\lfloor \sqrt{n}\rfloor$．集合 $D(n)$ 中的元素从小到大依次是

进而，$|D(n)|=\lfloor \sqrt{4n+1}\rfloor -1$．

首先，对于 $1\le i\le s$，可以证明 $\lfloor {\displaystyle \frac{n}{\lfloor n/i\rfloor }}\rfloor =i$．令 $d=\lfloor {\displaystyle \frac{n}{i}}\rfloor$，需要证明 $\lfloor {\displaystyle \frac{n}{d}}\rfloor =i$．写成不等式，这相当于已知 ，需要证明 ．已知条件可以写作 ，因此，只需要证明 ${\displaystyle \frac{i}{d}}\le 1$，亦即 $i\le d=\lfloor {\displaystyle \frac{n}{i}}\rfloor$．这等价于 $i\le {\displaystyle \frac{n}{i}}$，这对于所有 $1\le i\le s\le \sqrt{n}$ 都成立．

这一结果实际上说明，映射 $i\mapsto \lfloor {\displaystyle \frac{n}{i}}\rfloor$ 构成集合 $\{i:1\le i\le s\}$ 和集合 $\{\lfloor {\displaystyle \frac{n}{i}}\rfloor :1\le i\le s\}$ 之间的双射．由于 $i$ 各不相同，$\lfloor {\displaystyle \frac{n}{i}}\rfloor$ 也各不相同．两个集合唯一有可能相同的元素就是 $s$ 与 $\lfloor {\displaystyle \frac{n}{s}}\rfloor$．所以，$|D(n)|=2s-[s=\lfloor n/s\rfloor ]$．

要得到 $|D(n)|$ 最终的表达式，需要考察何时 $s=\lfloor {\displaystyle \frac{n}{s}}\rfloor$ 成立．

• 当 $s=\lfloor {\displaystyle \frac{n}{s}}\rfloor$ 时，总有 ，亦即 ．此时，有 ．又因为 $4n+1$ 一定是奇数，左侧可以等价地松弛到 $4s^2$，所以该条件就等价于 ，亦即 $\lfloor \sqrt{4n+1}\rfloor =2s$．
• 当 时，总有 $s+1\le {\displaystyle \frac{n}{s}}$，亦即 $s^2+s\le n$．又因为 ，就有 ．这就等价于 ．再次利用 $4n+1$ 是奇数这一点，右侧可以等价地收紧到 $4(s+1{)}^2$，所以该条件就等价于 ，亦即 $\lfloor \sqrt{4n+1}\rfloor =2s+1$．

总结这两种情形，就得到 $|D(n)|=\lfloor \sqrt{4n+1}\rfloor -1$ 成立．

对于 $d\in D(n)$，所有满足 $\lfloor {\displaystyle \frac{n}{i}}\rfloor =d$ 的整数 $i$ 的取值范围为

$$\lfloor \frac{n}{d+1}\rfloor +1\le i\le \lfloor \frac{n}{d}\rfloor .$$

因为 $\lfloor {\displaystyle \frac{n}{i}}\rfloor =d$ 相当于不等式

这进一步等价于

利用 $i\in {\mathbf{N}}_{+}$ 这一点，可以对该不等式取整，它就等价于

$$\lfloor \frac{n}{d+1}\rfloor +1\le i\le \lfloor \frac{n}{d}\rfloor .$$

对于 $m\in D(n)$，有 $D(m)\subseteq D(n)$．

设 $m=\lfloor {\displaystyle \frac{n}{k}}\rfloor$，那么，因为对于所有 $i\in {\mathbf{N}}_{+}$，都有

$$\lfloor \frac{m}{i}\rfloor =\lfloor \frac{\lfloor n/k\rfloor }{i}\rfloor =\lfloor \frac{n}{ki}\rfloor \in D(n),$$

所以，$D(m)\subseteq D(n)$．其中，第二个等号用到了 取整函数 关于嵌套分式的性质．

对于正整数 $n$ 和正实数 $\alpha ,\beta$，设

$$D(n,\alpha ,\beta )=\{\lfloor \frac{n^{\alpha }}{i^{\beta }}\rfloor :i=1,2,\cdots ,\lfloor n^{\alpha /\beta }\rfloor \}.$$

那么，有

1. $|D(n,\alpha ,\beta )|\le 2n^{\alpha /(1+\beta )}$．

2. 对于 $d\in D(n,\alpha ,\beta )$，使得 $\lfloor {\displaystyle \frac{n^{\alpha }}{i^{\beta }}}\rfloor =d$ 成立的 $i$ 的取值范围为

   $$\lfloor \frac{n^{\alpha /\beta }}{(d+1{)}^{1/\beta }}\rfloor +1\le i\le \lfloor \frac{n^{\alpha /\beta }}{d^{1/\beta }}\rfloor .$$

对于第一点，分两种情况：

• 当 $i\le {\displaystyle \frac{n^{\alpha }}{i^{\beta }}}$ 时，有 $i\le n^{\alpha /(1+\beta )}$，所以 $\lfloor {\displaystyle \frac{n^{\alpha }}{i^{\beta }}}\rfloor$ 至多有 $n^{\alpha /(1+\beta )}$ 种取值．
• 当 时，有 ，进而有 ，所以 $\lfloor {\displaystyle \frac{n^{\alpha }}{i^{\beta }}}\rfloor$ 也至多只有 $n^{\alpha /(1+\beta )}$ 种取值．

综合两种情形，就有 $|D(n,\alpha ,\beta )|\le 2n^{\alpha /(1+\beta )}$．

对于第二点，$\lfloor {\displaystyle \frac{n^{\alpha }}{i^{\beta }}}\rfloor =d$ 就等价于

对该不等式取整，就得到第二个命题．

根据前文分析，可以对于每一块相同的 $\lfloor {\displaystyle \frac{n}{i}}\rfloor$ 一起计算．时间复杂度为 $O(T\sqrt{n})$．

令 $a_0=0$．假设击杀所有前 $(i-1)$ 只怪兽需要 $T(k,i-1)$ 次攻击，第 $i$ 只怪兽的血量为 $a_i$．由于击杀第 $(i-1)$ 只怪兽时，需要攻击它 $\lceil a_{i-1}/k\rceil$ 次，这些攻击都可以延伸到第 $i$ 只怪兽．因此，要击杀第 $i$ 只怪兽，只需要再攻击 $max\{0,\lceil a_i/k\rceil -\lceil a_{i-1}/k\rceil \}$ 次．由此，总的攻击次数为

$$T(k,n)=\sum _{i=1}^{n}max(0,\lceil \frac{a_i}{k}\rceil -\lceil \frac{a_{i-1}}{k}\rceil ).$$

由于题目涉及的 $n,k$ 都比较大，对每个 $k$ 分别计算该和式并不可行．可以考虑对每个 $i=1,2,\cdots ,n$，都维护数列 $\{T(k,i){\}}_k$．初始时，设 $T(k,0)\equiv 0$．假设数列 $\{T(k,i-1){\}}_k$ 已知，考虑如何对它进行修改才能得到数列 $\{T(k,i){\}}_k$．根据前文分析，只需要对数列的第 $k$ 项增加 $max(0,\lceil {\displaystyle \frac{a_i}{k}}\rceil -\lceil {\displaystyle \frac{a_{i-1}}{k}}\rceil )$ 即可．利用二维数论分块，可以将这一修改操作拆分成 $O(\sqrt{a_{i-1}}+\sqrt{a_i})$ 段区间修改操作，且每段区间上增加的值是固定的．最后得到的数列 $\{T(k,n){\}}_k$ 就是答案．

由于题目涉及一系列区间加操作，且查询只发生所有修改完成后．所以，可以通过维护差分序列进行区间加修改，最后通过求前缀和得到所求数列．总的时间复杂度为 $O(\sum \sqrt{a_i})$．本题也存在其他解法．