Привет 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$$$ — размер блока) и для того, чтобы достичь асимптотики с аккреманом под корнем нам нужно знать a(n), чтобы поставить $$$B = \sqrt{n * \varphi^{-1} {(n)}}$$$, а для этого нужно знать $$$\varphi^{-1} {(n)}$$$. Таким образом все сводится к быстромы вычислению $$$\varphi^{-1} {(n)}$$$. Возможно ли это сделать?