Дан массив целых чисел a(len(a) < 10^5, 1 <= a[i] <= 10^9)
дано q запросов двух типов
В первом из них заданы два числа x(0 <= x < len(a)) и y(1 <= y <= 10^9) требуется изменить елемент массива а с позицией x на y
Во втором же заданы два числа: l,r(0 <= l < len(a), 0<= r < len(a), l < r) требуется найти два разных таких индекса x1,x2 принадлежащих отрезку от l до r включительно таких что их НОД будет максимально возмжным из всех пар(вывести его)
Я умею решать эту задачу полным перебором O(q*n^2) но мне лично интересно узнать есть ли решение за нормальную асимптотику(O(q*log(N))).
Auto comment: topic has been translated by waipoli (original revision, translated revision, compare)
секунды?
Неуверен что правильно понял ваш вопрос, можете уточнить?
Я бы хотел узнать лимит на секунды, у меня есть идея но она возможно не влезет в лимит секунд
Я думаю что да секунды 2, но тут больше вопрос в идее
Слишком много хочешь, запрос за логарифм это как-то слишком круто, думаю круче чем за линию не получится
Возможно
А как за линию? :)
Лично я лучше чем q*N*³✓N*logN не придумала, надеюсь кто-то всё таки улучшит асимптотику
$$$\sqrt[3]n$$$? Но тут $$$a[i] \leq 10^9$$$, даже решить задачу на 1 запрос с ограничениями автора никак не выйдет, но я могу предложить решение, которое реально решает задачу автора, если $$$a[i] \leq n$$$. Сначала решим задачу без обновлений, будем использовать алгоритм Мо, все довольно просто: проходимся по делителям числа, изменяем счетчик для каждого делителя и потом находим максимум среди тех, где счетчик $$$\geq 2$$$. Однако нужно быстро находить максимум, но сет держать не можем, поэтому сделаем корнячку, как в https://codeforces.com/blog/entry/83248 и теперь можно находить ответ на запрос за $$$\sqrt n$$$. Пора добавить обновления, для этого просто перепишем все на 3D Мо, условно как в разборе 940F и задача решена!
Асимптотика $$$O(n^{5/3})*128$$$, так как максимальное количество делителей среди чисел $$$\leq 10^5$$$ — это 128.
,