启发式合并

再次垫底$\text{.jpg}$ $\text{score：20 + 0 + 10 = 30 rk：27/29}$ Problem A：sign题面 题解这题贼水，但我没想出来。。 我大概以为这不是数学所以没想到代入，或者是我忘记该点值表示可以 $O (\log A)$ 反正全村就我没到及格线 题解懒得写了，就搬出题人给的吧 事实上，这个做法不能通过。 考虑上面做法复杂度瓶颈是快速幂。一个简单的$\text{trick}$是对于一个固定的 $son_u = k$，令 $M = \lceil \sqrt{A} \rceil$，预处理出 $k^0, k^1, k^2, …, k^{M - 1}$ 以及 $(k^M)^0, (k^M)^1, …, (k^M)^{M - 1}$。这样单次求某个点值就可以用 $O (1)$ 次算术运算求得。 时间复杂度为 $O ((n + \sqrt{A})\sqrt{n})$。 以上是出题人提供题解 代码123456789101112131415161718192021222324252627282930313233343536373839404142 ...