GSS4.

Собственно, нужно уметь брать сумму на отрезке и уметь каждый элемент отрезка заменять квадратным корнем из него, округленным вниз. Сумма всех элементов изначально не превосходит 10¹⁸

Я придумал решение за ( и я не уверен ли это). Идея тупая: каждое число станет единицей, если взять корень 7 раз. Тогда заведем 7 декартовых деревьев, первое из которых будет хранить текущий массив, второе — корни из его элементов, третье — корни из корней и так далее. при запросе на замену на корень вырежем из каждого нужный отрезок и сделаем циклический сдвиг вырезанных отрезков. Отрезок дерева, который мы вытащили из самого первого дерева зальем единичками (после этого вставим в последнее).

Такое решение дает ТЛ. Интересно, можно ли быстрее и/или проще?