Заметим, что если мы поделим число $$$x$$$ ($$$1 \leq x \leq 10^9$$$) 30 раз на число большее единицы, то оно станет равно нулю, так как после каждого деления число уменьшается хотя бы в два раза. Будем поддерживать в сете позиции чисел больших единицы и делить только на них.
- Заведем структуру данных, которая умеет отнимать $$$1$$$ на отрезке и находить максимум на отрезке, например, дерево отрезков. Сделаем $$$-= 1$$$ на ($$$l$$$, $$$r$$$), а затем, пока $$$\min(s_l, s_{l + 1}, \dots, s_r) = 1$$$, удалим из сета позицию минимума.
- Найдем двоичным поиском в сете первую позицию не единицы большую либо равную $$$l$$$. Затем будем переходить к следующей позиции в сете и делить на нее. Чтобы узнать значение в конкретной позиции, необходимо обратиться к структуре. Как только в результате деления был получен $$$0$$$, мы останавливаемся.
Время работы:
- Суммарно первый тип запросов будет работать за $$$\mathcal{O}(n \cdot \log(n) + q \cdot \log(n))$$$.
- Второй тип запросов будет работать за $$$\mathcal{O}(q \cdot \log(n) \cdot \log(maxC))$$$