Автокомментарий: текст был обновлен пользователем MAX11189 (предыдущая версия, новая версия, сравнить).

Будем считать, что числа в массиве только положительные. Придумал решение за q * log^2 * α(n) с использованием Segment Tree Beats.

Фиксируем левую границу l. Тогда gcd на [l, i] меняется не больше log C раз, так как каждое его изменение — уменьшение хотя бы в 2 раза. Как найти такие позиции i, где НОД меняется? Спуском по ДО или бинпоиском по спарсам. Пусть эти отрезки выглядят как [l, i[1]], [l, i[2]], ..., [l, i[k]], где k = O(log C). Тогда, если мы будем увеличивать r от 0 до n, для каждого l ответ на отрезке [l, r] будет становиться всё оптимальнее. Когда он может стать оптимальнее при переходе от r — 1 к r? Если r — это правая граница i[j] для нашего l. Таких случаев всего n logC. Что же происходит с ответом для l, если переход от r — 1 к r не обновляет НОД? Наш ответ изменится ровно на gcd[l, r] * a[r], так как сумма увеличится на a[r], а НОД не изменится.

Отсортируем запросы в порядке увеличения правой границы и будем отвечать на них именно в таком порядке. Каждому l сопоставим пару чисел {k, b} такую, что k — текущий ответ, b — gcd на текущем отрезке. Тогда переход от r — 1 к r — это замена пары {k, b}, если r меняет НОД, или добавление к k: k += gcd * a[r], или k += b * a[r]. А запрос [l, r] — это узнать максимум среди всех k, которые принадлежат элементам с l по r, так как левая граница нашего отрезка обязательно будет на этом отрезке. Для выполнения этих запросов можно использовать Кинетическое дерево отрезков — оно делает именно те операции, которые нам нужны, и именно для этого нам нужно ограничение a[i] >= 0.

UPD: При увеличении r и смене НОДа ответ может стать менее оптимальным, чем был. Тогда к этому всему нам еще придется прикрутить Segment Tree Beats на максимум исторических максимумов на отрезке — мы обновляем k для каждого l, а также должны искать для всех k на позициях с l по r их исторически максимальное значение.

last task

Можно решить за Q*log^2 или Q*log любым двухмерным ДО

Известно что для зафиксированного L, у нас будет не больше logA различных значений gcd(l;r). Очевидно, что для фиксированного L, и фиксированного значения gcd(l,r) всегда оптимально брать самый правый R дающий такой нод.

Определим F(L,R) = gcd(l,r)*sum(l,r).

Для каждого L предпочитаем индексы RX(L) — самые правые границы отрезков где НОД не меняется. Можно сделать за Nlog разреж.таблицой + бин поиском

Тогда ответом на запрос [L,R] будет максимум из следующих значений:

• F(tl, RX(tl)[j]) //для L <= tl <= R, и RX(tl)[j] <= R
• F(tl, R) //для L <= tl <= R, и R из оригинального запроса

Первое значение можно считать, представив точки с координатами (X,Y) = (L, RX(L)[j]) = F(L, Rx(L)[j]). Находить максимум можно запросом к подпрямоугольнику (L,L, R,R)

Второе значение симметрично первому, и его вообще можно находить за O(logA), предпосчитав LX(R) — симметрично RX(L)

....