Зручні партії#13104

Зручні партії (Розбір)

Ключове спостереження. Зафіксуймо лівий кінець і розширюймо групу праворуч. Значення \gcd(a_i, \ldots, a_j) утворюють ланцюжок дільників, і щоразу, коли значення змінюється, воно стає власним дільником попереднього, тобто щонайменше вдвічі меншає. Оскільки a_i \le 10^9 < 2^{30}, різних значень не більше ніж . Отже, префіксні gcd будь-якого відрізка розбиваються на O(\log A) блоків послідовних префіксів з однаковим gcd, і те саме справджується для суфіксів.

Дерево відрізків. У кожній вершині зберігаємо: — кількість зручних груп усередині неї; — gcd усієї вершини; — список різних префіксних gcd у порядку зростання префікса, кожен разом з кількістю префіксів, що його мають; — те саме для суфіксів. Листок зі значенням має \mathrm{cnt} = [x > 1] і \mathrm{pre} = \mathrm{suf} = ((x, 1)).

Щоб об'єднати лівого сина з правим сином : \mathrm{tot} = \gcd(L.\mathrm{tot}, R.\mathrm{tot}); — це , після якого йдуть блоки (\gcd(L.\mathrm{tot}, g), c) для з , причому однакові сусіди зливаються; — симетрично. Нарешті, \mathrm{cnt} = L.\mathrm{cnt} + R.\mathrm{cnt} + \mathrm{cross}, де — кількість зручних груп, що перетинають середину, тобто пар (суфікс , префікс ) з \gcd(s, g) > 1 з урахуванням кратностей.

Підрахунок пар через середину. Якщо \gcd(s, g) > 1 для суфіксного gcd і префіксного gcd , то це справджується і для кожного коротшого суфікса та кожного коротшого префікса, бо їхні gcd кратні і . Тож коли суфікс росте, множина префіксів, що дають з ним gcd більший за , є префіксом , який може лише зменшуватися. Проходимо у порядку зростання довжини й рухаємо вказівник по назад, поки поточна пара має gcd , підтримуючи сумарну кратність решти блоків префіксів. Це O(\log A) обчислень gcd на одне об'єднання.

Операції. Оновлення змінює листок і заново об'єднує його O(\log n) предків. Запит [l, r] згортає O(\log n) канонічних вершин зліва направо тим самим об'єднанням; акумулятору потрібні лише , і . Відповідь може сягати n(n+1)/2 \approx 4.5 \cdot 10^{10}, тож потрібні 64-бітні цілі.

Складність — O((n + q) \log n \log A) обчислень gcd, де A = 10^9. Пам'ять — , бо вершина довжини має списки довжини не більше ніж \min(k, 31).