题解：CF1687D Cute number

ArSGTExp · 2026-03-06 11:43:23 · 题解

注意到三个当时的 LGM 和小芬图本场过了两个，艾利克斯维本场只过了一个，所以我不会 2E 是不是正常的。/ll

感觉至少在思维难度和思维性上确实没有 2E 难吧，评分到 *2900 感觉主要原因是 Petr 和 hos 不会。

首先显然能注意到合法区间是所有形如 [x^2, x(x + 1)](x \in \mathbf{N^+}) 的并，称区间 [x^2, x(x + 1)] 为 x 的段。

那么假设 a 的值域为 V，那么直接把 a_1 变成 V^2 就完事了，所以我们现在只需要考虑 a_1 = x^2 + k, x \in [1, V - 1], k \in [0, x] 的情况能否满足即可。

确定了 x 之后，每个 a_i + k 在谁的段里就被确定了（因为 a_1 是最小的，跨越 x 之后的段的壁垒至少需要 x + 1，但是 k_{\max} = x），这样可求出每个 a_i 限制 k 的上界和下界，如果最后搞出来的不是空集就对了。

现在你的复杂度是 nV 的，但是发现对于 x，后面最多有 \frac{n}{x} 段，对每个段而非每个点考虑，随便维护下块内的点就可以做到 V \operatorname{polylog}。