Привет codeforces!
Недавно я писал корневую декомпозицию + снм, причем использовать снм мне приходилось только в случае, если запрос содержит блок целиком. Какая будет асимптотика этого решения?
Вам может показаться очевидным, что асимптотика будет $$$O(n \cdot \sqrt{n \cdot \varphi^{-1} {(n)}})$$$ ($$$\varphi^{-1} {(n)}$$$ — обратная функция Аккермана).
Но на самом деле асимптотика — $$$O(n \cdot B \cdot \varphi^{-1}{(n)} + \frac{n ^ 2}{B})$$$ ($$$B$$$ — размер блока) и для того, чтобы достичь асимптотики с аккреманом под корнем нам нужно знать $$$\varphi^{-1}{(n)}$$$, чтобы поставить $$$B = \sqrt{n * \varphi^{-1} {(n)}}$$$, а для этого нужно знать $$$\varphi^{-1} {(n)}$$$. Таким образом все сводится к быстромы вычислению $$$\varphi^{-1} {(n)}$$$. Возможно ли это сделать?









Is it theoretical or practical question?
For practical reasons, this should not bother you. For all reasonable values of $$$n \le 10^{18}$$$, $$$\alpha(n) \le 4$$$ (could be easily calculated, using the recurrence from wikipedia). You can put $$$B = \sqrt{n}$$$, or, if you want to achieve the optimal time, then you need to benchmark the code to get know, which parts of it are more fast and which are more slow to adjust the constant $$$B$$$ properly. It will be somewhere near $$$\sqrt{n}$$$, but could easily be $$$5$$$ times less than it, or $$$5$$$ times greater — all depends on the constant factors.
For theoretical reasons, it is easy to calculate the inverse Ackerman function say in $$$\mathcal{O}(n)$$$. You just need to follow the recurrence, and stop the calculations, once the values are too big. The following is a sketch of the solution, though you need to be careful with big integers and overflowing.
The Ackerman function grows so fast that it should be not so hard to prove that the code above produces correct answer, though it doesn't calculates all of the required values.
Известно, что обратная функция Аккермана вычислима за линейное время: doi.org/10.3233/FI-2021-2077.
Учитывая, что для нужной нам прямой функции Аккермана $$$\alpha \colon n \mapsto A(n,n)$$$ верно следующее
то ее обратную можно в простейшем виде посчитать как (я использовал округление вверх для промежуточных значений)
Можно, конечно, использовать линейную или еще какую-нибудь интерполяцию, что приведет к
P. S. $$$B = \sqrt{n / \alpha(n)}$$$.