Editorial

Перший важливий факт для розв'язання цієї задачі — $gcd$ змінюється не більше, ніж $lo g A$ разів. Це можна просто показати, нехай в нас $g_{1}, g_{2}$ , де $g_{2} = g c d (g_{1}, x)$ . Тепер, якщо $g_{1} \neq = g_{2}$ , то $\frac{g _{1}}{g _{2}} > 1$ (бо $g_{2}$ ділить $g_{1}$ ), тобто хоча б $2$ , що значить, що кожен раз коли $gcd$ змінюється, воно зменшується хоча б вдвічі.

Тепер, давайте для кожної позиції $i$ знайдемо позиції $j$ зліва і $k$ справа, де $gcd$ змінюється. Але, треба запам'ятати для кожного $gcd$ останню позицію, так, щоб довжина відрізка [ $j; i$ ] чи [ $i; k$ ] була максимальною. Для кожної позиції в нас є $O (lo g A)$ позицій, де $gcd$ змінюється.

Зафіксуймо праву границю $r$ , тоді щоб відповідати на запити підтримуймо масив $b$ , що $b_{i}$ — найбільша відповідь для відрізків, що мають ліву границю в $i$ , і їх права границю менше рівна $r$ .

Щоб відповісти на запит $[l; r]$ питаємо максимум в масиві $b$ на відрізку $[l; r]$ і треба перевірити всі відрізки, які починались в цьому відрізку, але закінчились лівіше. Тоді $a_{l}$ точно було взято у відрізок, то перевіримо всі відрізки, де змінюється $gcd$ справа від $l$ .

Таке можна розв'язувати офлайн за допомогою дерева відрізків і сортуванням запитів, чи онлайн, за допомогою персистентного дерева відрізків.

Розв'язок з персистентним деревом відрізків має асимптотику $O (N lo g N lo g N + Q \cdot (lo g A + lo g N))$ . Інші розв'язки, які відомі мені, мають таку саму асимптотику, але кращу константу, що робить їх значно швидшими.

На початку планувалось зробити всі запити онлайн щоб було цікавіше розв'язувати задачу, але через деякі причини було вирішено зробити задачу стандартною — хто хоче розв'язувати офлайн — нехай розв'язує