Козак Вус та НСД#202

Козак Вус та НСД (Розбір)

Спершу зрозуміймо, що взагалі означає «дізнатися масив ».

Запит [l, r] повідомляє суму b_l + \ldots + b_r, тобто різницю префіксних сум P_r - P_{l-1}, де P_0 = 0. Отже, кожен запит — це ребро між вершинами l-1 і у графі на вершинах \{0, 1, \ldots, n\} з вагою \gcd(a_l, \ldots, a_r). Щоб відновити всі P_i (а отже й увесь масив ), цей граф має стати зв'язним. Тому відповідь — вага мінімального кістякового дерева на n+1 вершині.

Тепер скористаємось властивістю НСД: чим довший відрізок, тим менший (точніше, ділить) його НСД. Тому найдешевше ребро, що виходить із вершини ліворуч, — це ребро аж до вершини з вагою \mathrm{pre}_i = \gcd(a_1, \ldots, a_i), а найдешевше праворуч — ребро до вершини з вагою \mathrm{suf}_{i+1} = \gcd(a_{i+1}, \ldots, a_n). Отже, найдешевше інцидентне ребро вершини має вагу

\min\bigl(\mathrm{pre}_i,\; \mathrm{suf}_{i+1}\bigr).

Звідси випливає проста структура кістякового дерева: з'єднаємо вершини і ребром на весь масив, вага якого дорівнює G = \gcd(a_1, \ldots, a_n), а кожну проміжну вершину (1 \le i \le n-1) підвісимо її найдешевшим ребром — або до , або до . Виходить дерево, і за властивістю розрізу кожне з цих ребер безпечне. Отже,

\mathrm{MST} = G + \sum_{i=1}^{n-1} \min\bigl(\mathrm{pre}_i,\; \mathrm{suf}_{i+1}\bigr).

Залишилось швидко перераховувати цю суму після кожної зміни a_i.

Тут допомагає ще одна властивість НСД: послідовність префіксних НСД незростаюча за подільністю, і щоразу, коли значення змінюється, воно зменшується щонайменше вдвічі. Тому різних значень серед \mathrm{pre}_1, \ldots, \mathrm{pre}_n лише \mathcal{O}(\log A), тобто близько ; те саме для суфіксних. Іншими словами, обидві функції — кусково-сталі з десятками блоків.

Тому будуємо дерево відрізків на НСД із точковим оновленням. Щоб дістати список блоків префіксних НСД, спускаємось по дереву: маючи поточне значення, двійковим пошуком знаходимо найдальшу позицію, де воно ще не змінилося, — це \mathcal{O}(\log n) на блок, разом \mathcal{O}(\log n \log A). Аналогічно для суфіксних.

Маючи два списки блоків, зливаємо їх «двома вказівниками», як дві кусково-сталі функції: на кожній спільній ділянці значення \min(\mathrm{pre}, \mathrm{suf}) стале, тому внесок — це добуток цього мінімуму на довжину ділянки.

Загальна складність — \mathcal{O}\bigl((n + q)\log n \log A\bigr). Суми сягають n \cdot \max a_i = 10^{14}, тому обов'язково 64-бітний тип. Перевірте окремий випадок n = 1: сума порожня, і відповідь дорівнює просто a_1.